Submission #60958848
Source Code Expand
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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 |
|
|
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 |