Submission #60958848


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;
//
vector<ll> get_range(const vector<ll>& sorted_coords, ll low, ll high) {
auto start = lower_bound(sorted_coords.begin(), sorted_coords.end(), low);
auto end = upper_bound(sorted_coords.begin(), sorted_coords.end(), high);
return vector<ll>(start, end);
}
int main() {
ll N, M, Sx, Sy;
cin >> N >> M >> Sx >> Sy;
//
map<ll, vector<ll>> x_to_ys; // xy
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
using ll = long long;

// 二分探索で範囲内の値を取得
vector<ll> get_range(const vector<ll>& sorted_coords, ll low, ll high) {
    auto start = lower_bound(sorted_coords.begin(), sorted_coords.end(), low);
    auto end = upper_bound(sorted_coords.begin(), sorted_coords.end(), high);
    return vector<ll>(start, end);
}

int main() {
    ll N, M, Sx, Sy;
    cin >> N >> M >> Sx >> Sy;

    // 家の位置を読み込む
    map<ll, vector<ll>> x_to_ys; // 各x座標におけるy座標のリスト
    map<ll, vector<ll>> y_to_xs; // 各y座標におけるx座標のリスト
    for (ll i = 0; i < N; ++i) {
        ll x, y;
        cin >> x >> y;
        x_to_ys[x].push_back(y);
        y_to_xs[y].push_back(x);
    }

    // 各リストをソートしておく
    for (auto& [_, ys] : x_to_ys) sort(ys.begin(), ys.end());
    for (auto& [_, xs] : y_to_xs) sort(xs.begin(), xs.end());

    // 移動の指示を読み込む
    vector<pair<char, ll>> moves(M);
    for (ll i = 0; i < M; ++i) {
        char d;
        ll c;
        cin >> d >> c;
        moves[i] = {d, c};
    }

    // 現在の位置
    ll x = Sx, y = Sy;

    // 訪問済みの家の記録
    set<pair<ll, ll>> visited;

    // 各移動を処理
    for (const auto& [dir, dist] : moves) {
        ll nx = x, ny = y;

        // 移動後の座標を計算
        if (dir == 'U') ny += dist;
        else if (dir == 'D') ny -= dist;
        else if (dir == 'L') nx -= dist;
        else if (dir == 'R') nx += dist;

        // 移動方向ごとに家を探索
        if (dir == 'U' || dir == 'D') {
            // 縦移動: x固定でy範囲を探索
            if (x_to_ys.count(x)) {
                auto ys = get_range(x_to_ys[x], min(y, ny), max(y, ny));
                for (ll cy : ys) visited.insert({x, cy});
            }
        } else {
            // 横移動: y固定でx範囲を探索
            if (y_to_xs.count(y)) {
                auto xs = get_range(y_to_xs[y], min(x, nx), max(x, nx));
                for (ll cx : xs) visited.insert({cx, y});
            }
        }

        // 現在位置を更新
        x = nx;
        y = ny;
    }

    // 出力
    cout << x << " " << y << " " << visited.size() << endl;

    return 0;
}

Submission Info

Submission Time
Task D - Santa Claus 2
User VIP1109
Language C++ 20 (gcc 12.2)
Score 425
Code Size 2449 Byte
Status AC
Exec Time 1897 ms
Memory 44512 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 2
AC × 25
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All hand.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
hand.txt AC 1 ms 3440 KiB
random_01.txt AC 64 ms 6288 KiB
random_02.txt AC 64 ms 6288 KiB
random_03.txt AC 64 ms 6424 KiB
random_04.txt AC 246 ms 28316 KiB
random_05.txt AC 270 ms 35160 KiB
random_06.txt AC 1104 ms 14832 KiB
random_07.txt AC 820 ms 24592 KiB
random_08.txt AC 345 ms 38752 KiB
random_09.txt AC 424 ms 44512 KiB
random_10.txt AC 96 ms 13088 KiB
random_11.txt AC 628 ms 20756 KiB
random_12.txt AC 1134 ms 22124 KiB
random_13.txt AC 164 ms 12984 KiB
random_14.txt AC 1205 ms 21812 KiB
random_15.txt AC 1521 ms 22164 KiB
random_16.txt AC 1441 ms 22988 KiB
random_17.txt AC 1600 ms 22324 KiB
random_18.txt AC 1117 ms 21744 KiB
random_19.txt AC 1723 ms 22564 KiB
random_20.txt AC 293 ms 19400 KiB
random_21.txt AC 1338 ms 21904 KiB
random_22.txt AC 1897 ms 23080 KiB
sample_01.txt AC 1 ms 3472 KiB
sample_02.txt AC 1 ms 3472 KiB


2025-06-07 (Sat)
09:28:18 +09:00