Submission #00073
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | #include <iostream> #include <vector> using namespace std; typedef long long ll; typedef enum { //rotate F = 0, //direction U = 0, R = 1, D = 2, L = 3 } Dir; struct st { ll x, y; char d; char ang; }; struct SegmentTree { vector<st> dat; int size; st merge(st l, st r) { st res; st r_cp = r; //rotate switch (l.d) { case L: r.y = r_cp.x; r.x = -r_cp.y; break ; case R: r.y = -r_cp.x; r.x = r_cp.y; break ; case D: r.y = -r_cp.y; r.x = -r_cp.x; } //vector switch (l.ang) { case F: res.y = l.y + r.y; res.x = l.x + r.x; break ; case L: res.y = l.y + r.x; res.x = l.x - r.y; break ; case R: res.y = l.y - r.x; res.x = l.x + r.y; break ; } //direction res.d = (l.d + l.ang + r.d) % 4; res.ang = r.ang; return res; } void init( int n) { size = 1; while (size < n) { size *= 2; } dat.resize(2 * size, (st){0, 0, 0, 0}); } void update( int key, st a) { key += size - 1; dat[key] = a; while (key > 0) { key = (key - 1) / 2; dat[key] = merge(dat[key * 2 + 1], dat[key * 2 + 2]); } } st top( void ) { return dat[0]; } }; SegmentTree seg; int main() { ll n, q; ll sx, sy; ll t; char d; cin >> n >> q; cin >> sx >> sy; seg.init(n + 1); seg.update(0, (st){sx, sy, U, F}); for ( int i = 1; i <= n; i++) { seg.update(i, (st){0, 1, U, F}); } //cout << seg.top().x << ' ' << seg.top().y << endl; for ( int i = 0; i < q; i++) { cin >> t >> d; if (d == 'L' ) { seg.update(t, (st){0, 1, U, L}); } else { seg.update(t, (st){0, 1, U, R}); } cout << seg.top().x << ' ' << seg.top().y << endl; } return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0012 - 創世の種 |
ユーザー名 | ei1710 |
投稿日時 | 2019-04-28 01:37:58 |
言語 | C++14 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 2509 Byte |
最大実行時間 | 288 ms |
最大メモリ使用量 | 11360 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in_1.txt | AC | 33 ms | 604 KB |
1
|
in_2.txt | AC | 30 ms | 2104 KB |
1
|
in_3.txt | AC | 16 ms | 2028 KB |
1
|
in_4.txt | AC | 29 ms | 2124 KB |
1
|
in_5.txt | AC | 288 ms | 9088 KB |
1
|
in_6.txt | AC | 266 ms | 11360 KB |
1
|
in_7.txt | AC | 22 ms | 5308 KB |
1
|
in_8.txt | AC | 190 ms | 7060 KB |
1
|
in_9.txt | AC | 200 ms | 8596 KB |
1
|
in_10.txt | AC | 191 ms | 2108 KB |
1
|