# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
122033 | 2019-06-27T11:59:51 Z | yusufake | 게임 (IOI13_game) | C++ | 7320 ms | 256000 KB |
#include<bits/stdc++.h> #include "game.h" using namespace std; #define _ int v, int tl, int tr #define tm (tl + tr >> 1) typedef long long ll; typedef pair < int , int > pp; const int mod = 1e9 + 7; const int x_N = 22000 * 23; const int y_N = 22000 * 23 * 23; int x_to_Y[x_N],x_L[x_N],x_R[x_N],x_id = 1; int y_L[y_N],y_R[y_N],y_id; ll s[y_N]; // segment tree values are stored only for -y axis // 0 is empty node // s[0] should be ineffective element // x_to_Y[0], L[0], and R[0] should be 0 // 1 is the root of the -x axis segment tree // x_to_Y[v] is the root of the segment tree of the interval that corresponds to node 'v' in -x axis segment tree ll gcd(ll u, ll v) { ll r; while (v != 0) { r = u % v; u = v; v = r; } return u; } ll qry_y(_, int ly, int ry) { if(ly > tr || ry < tl || !v) return 0; if (ly <= tl && tr <= ry) return s[v]; return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,ly,ry)); } ll qry_x(_, int lx, int rx, int ly, int ry) { if(lx > tr || rx < tl) return 0; if (lx <= tl && tr <= rx) return qry_y(x_to_Y[v], 0, mod, ly, ry); return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,lx,rx,ly,ry)); } void up_y(_, int posy, int r1, int r2, ll t){ if(tl == tr){ s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t; return; } if(posy > tm) { if(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); } else { if(!y_L[v]) y_L[v] = ++y_id; up_y(y_L[v],tl,tm, posy,y_L[r1],y_L[r2],t); } s[v] = gcd(s[ y_L[v] ] , s[ y_R[v] ]); } void up_x(_, int posx, int posy, ll t){ if(tl < tr){ if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); } else { if(!x_L[v]) x_L[v] = ++x_id; up_x(x_L[v],tl,tm, posx,posy,t); } } if(!x_to_Y[v]) x_to_Y[v] = ++y_id; up_y(x_to_Y[v],0,mod,posy,x_to_Y[ x_L[v] ],x_to_Y[ x_R[v] ],(tl==tr?t:-1)); } void update(int posx, int posy, ll t){ up_x(1,0,mod,posx,posy,t); } ll calculate(int lx, int ly, int rx, int ry){ return qry_x(1,0,mod,lx,rx,ly,ry); } void init(int a, int b) { memset(s , 0 , sizeof s); memset(x_L , 0 , sizeof x_L); memset(x_R , 0 , sizeof x_R); memset(y_L , 0 , sizeof y_L); memset(y_R , 0 , sizeof y_R); memset(x_to_Y , 0 , sizeof x_to_Y); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 145 ms | 188536 KB | Output is correct |
2 | Correct | 146 ms | 188536 KB | Output is correct |
3 | Correct | 145 ms | 188536 KB | Output is correct |
4 | Correct | 140 ms | 188504 KB | Output is correct |
5 | Correct | 142 ms | 188452 KB | Output is correct |
6 | Correct | 140 ms | 188452 KB | Output is correct |
7 | Correct | 140 ms | 188536 KB | Output is correct |
8 | Correct | 143 ms | 188408 KB | Output is correct |
9 | Correct | 139 ms | 188488 KB | Output is correct |
10 | Correct | 137 ms | 188536 KB | Output is correct |
11 | Correct | 138 ms | 188508 KB | Output is correct |
12 | Correct | 137 ms | 188536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 137 ms | 188488 KB | Output is correct |
2 | Correct | 143 ms | 188424 KB | Output is correct |
3 | Correct | 140 ms | 188508 KB | Output is correct |
4 | Correct | 1275 ms | 192536 KB | Output is correct |
5 | Correct | 982 ms | 192896 KB | Output is correct |
6 | Correct | 1385 ms | 189828 KB | Output is correct |
7 | Correct | 1692 ms | 189640 KB | Output is correct |
8 | Correct | 1008 ms | 190164 KB | Output is correct |
9 | Correct | 1535 ms | 189548 KB | Output is correct |
10 | Correct | 1347 ms | 189108 KB | Output is correct |
11 | Correct | 141 ms | 188536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 137 ms | 188476 KB | Output is correct |
2 | Correct | 137 ms | 188488 KB | Output is correct |
3 | Correct | 139 ms | 188440 KB | Output is correct |
4 | Correct | 137 ms | 188536 KB | Output is correct |
5 | Correct | 141 ms | 188408 KB | Output is correct |
6 | Correct | 140 ms | 188568 KB | Output is correct |
7 | Correct | 138 ms | 188480 KB | Output is correct |
8 | Correct | 146 ms | 188536 KB | Output is correct |
9 | Correct | 142 ms | 188412 KB | Output is correct |
10 | Correct | 138 ms | 188524 KB | Output is correct |
11 | Correct | 137 ms | 188536 KB | Output is correct |
12 | Correct | 1869 ms | 192720 KB | Output is correct |
13 | Correct | 2616 ms | 189540 KB | Output is correct |
14 | Correct | 754 ms | 189176 KB | Output is correct |
15 | Correct | 2958 ms | 189424 KB | Output is correct |
16 | Correct | 792 ms | 189448 KB | Output is correct |
17 | Correct | 2004 ms | 190048 KB | Output is correct |
18 | Correct | 3174 ms | 189696 KB | Output is correct |
19 | Correct | 2665 ms | 189836 KB | Output is correct |
20 | Correct | 2741 ms | 189204 KB | Output is correct |
21 | Correct | 142 ms | 188408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 148 ms | 188408 KB | Output is correct |
2 | Correct | 145 ms | 188408 KB | Output is correct |
3 | Correct | 144 ms | 188408 KB | Output is correct |
4 | Correct | 138 ms | 188476 KB | Output is correct |
5 | Correct | 153 ms | 188488 KB | Output is correct |
6 | Correct | 278 ms | 188448 KB | Output is correct |
7 | Correct | 142 ms | 188536 KB | Output is correct |
8 | Correct | 145 ms | 188420 KB | Output is correct |
9 | Correct | 147 ms | 188536 KB | Output is correct |
10 | Correct | 136 ms | 188536 KB | Output is correct |
11 | Correct | 138 ms | 188536 KB | Output is correct |
12 | Correct | 1212 ms | 192528 KB | Output is correct |
13 | Correct | 1020 ms | 193008 KB | Output is correct |
14 | Correct | 1474 ms | 189736 KB | Output is correct |
15 | Correct | 1501 ms | 189432 KB | Output is correct |
16 | Correct | 986 ms | 190248 KB | Output is correct |
17 | Correct | 1778 ms | 189468 KB | Output is correct |
18 | Correct | 1404 ms | 189232 KB | Output is correct |
19 | Correct | 1847 ms | 192624 KB | Output is correct |
20 | Correct | 2615 ms | 189364 KB | Output is correct |
21 | Correct | 762 ms | 189108 KB | Output is correct |
22 | Correct | 3082 ms | 189368 KB | Output is correct |
23 | Correct | 823 ms | 189300 KB | Output is correct |
24 | Correct | 2031 ms | 189888 KB | Output is correct |
25 | Correct | 3217 ms | 189804 KB | Output is correct |
26 | Correct | 2683 ms | 189708 KB | Output is correct |
27 | Correct | 2692 ms | 189180 KB | Output is correct |
28 | Correct | 1238 ms | 189128 KB | Output is correct |
29 | Correct | 2886 ms | 192320 KB | Output is correct |
30 | Correct | 7320 ms | 189116 KB | Output is correct |
31 | Correct | 6861 ms | 189408 KB | Output is correct |
32 | Correct | 835 ms | 189048 KB | Output is correct |
33 | Correct | 1061 ms | 189020 KB | Output is correct |
34 | Correct | 1544 ms | 189304 KB | Output is correct |
35 | Correct | 2335 ms | 189984 KB | Output is correct |
36 | Correct | 4794 ms | 189476 KB | Output is correct |
37 | Correct | 3591 ms | 189768 KB | Output is correct |
38 | Correct | 3376 ms | 189312 KB | Output is correct |
39 | Correct | 2922 ms | 189892 KB | Output is correct |
40 | Correct | 142 ms | 188408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 143 ms | 188508 KB | Output is correct |
2 | Correct | 138 ms | 188436 KB | Output is correct |
3 | Correct | 139 ms | 188408 KB | Output is correct |
4 | Correct | 150 ms | 188408 KB | Output is correct |
5 | Correct | 138 ms | 188500 KB | Output is correct |
6 | Correct | 143 ms | 188508 KB | Output is correct |
7 | Correct | 142 ms | 188584 KB | Output is correct |
8 | Correct | 146 ms | 188508 KB | Output is correct |
9 | Correct | 143 ms | 188536 KB | Output is correct |
10 | Correct | 140 ms | 188480 KB | Output is correct |
11 | Correct | 141 ms | 188408 KB | Output is correct |
12 | Correct | 1217 ms | 192520 KB | Output is correct |
13 | Correct | 994 ms | 192792 KB | Output is correct |
14 | Correct | 1346 ms | 189604 KB | Output is correct |
15 | Correct | 1371 ms | 189516 KB | Output is correct |
16 | Correct | 983 ms | 190072 KB | Output is correct |
17 | Correct | 1460 ms | 189560 KB | Output is correct |
18 | Correct | 1336 ms | 189056 KB | Output is correct |
19 | Correct | 1873 ms | 192504 KB | Output is correct |
20 | Correct | 2751 ms | 189264 KB | Output is correct |
21 | Correct | 775 ms | 189184 KB | Output is correct |
22 | Correct | 3064 ms | 189336 KB | Output is correct |
23 | Correct | 811 ms | 189304 KB | Output is correct |
24 | Correct | 1988 ms | 189816 KB | Output is correct |
25 | Correct | 3362 ms | 189824 KB | Output is correct |
26 | Correct | 2828 ms | 189816 KB | Output is correct |
27 | Correct | 2526 ms | 189112 KB | Output is correct |
28 | Correct | 1116 ms | 189176 KB | Output is correct |
29 | Correct | 2924 ms | 192172 KB | Output is correct |
30 | Correct | 7234 ms | 189124 KB | Output is correct |
31 | Correct | 6868 ms | 189612 KB | Output is correct |
32 | Correct | 856 ms | 189380 KB | Output is correct |
33 | Correct | 1073 ms | 189264 KB | Output is correct |
34 | Correct | 1541 ms | 189432 KB | Output is correct |
35 | Correct | 2346 ms | 190124 KB | Output is correct |
36 | Correct | 4595 ms | 189884 KB | Output is correct |
37 | Correct | 3531 ms | 190004 KB | Output is correct |
38 | Correct | 3511 ms | 189500 KB | Output is correct |
39 | Runtime error | 1165 ms | 256000 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
40 | Halted | 0 ms | 0 KB | - |