Submission #60957837

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <tuple>
using namespace std;
using ll = long long;
// 座標を一意に表現するためのヘルパー
struct Coordinate {
    ll x, y;
    bool operator<(const Coordinate& other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};
int main() {
    ll N, M, Sx, Sy;
    cin >> N >> M >> Sx >> Sy;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <tuple>
using namespace std;
using ll = long long;

// 座標を一意に表現するためのヘルパー
struct Coordinate {
    ll x, y;
    bool operator<(const Coordinate& other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};

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

    // 家の座標を読み込む
    set<Coordinate> houses;
    for (ll i = 0; i < N; ++i) {
        ll x, y;
        cin >> x >> y;
        houses.insert({x, y});
    }

    // 移動の指示を読み込む
    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<Coordinate> 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') {
            ll start = min(y, ny), end = max(y, ny);
            for (auto it = houses.lower_bound({x, start}); it != houses.end() && it->y <= end; ++it) {
                if (it->x == x) visited.insert(*it);
            }
        } else {
            ll start = min(x, nx), end = max(x, nx);
            for (auto it = houses.lower_bound({start, y}); it != houses.end() && it->x <= end; ++it) {
                if (it->y == y) visited.insert(*it);
            }
        }

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

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

    return 0;
}

Submission Info

Judge Result