# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
121966 | 2019-06-27T09:58:28 Z | yusufake | 게임 (IOI13_game) | C++ | 7487 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) #define sol L[v],tl,tm #define sag R[v],tm+1,tr #define mp make_pair #define pb push_back #define st first #define nd second typedef long long ll; typedef pair < int , int > pp; const int mod = 1e9 + 7; const int N = 22000 * 27 * 27; int Y[N],L[N],R[N],id; ll s[N]; // 0 is empty node // s[0] should be ineffective element // Y[0], L[0], and R[0] should be 0 // 1 is the root of the -x axis segment tree // 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(sol,ly,ry) , qry_y(sag,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(Y[v], 0, mod, ly, ry); return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry)); } void up_y(_, int posy, int r1, int r2, ll t){ if(id == N - 5) while(1); if(tl == tr){ s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t; return; } if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); } else { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); } s[v] = gcd(s[ L[v] ] , s[ R[v] ]); } void up_x(_, int posx, int posy, ll t){ if(id == N - 5) while(1); if(tl < tr){ if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); } else { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); } } if(!Y[v]) Y[v] = ++id; up_y(Y[v],0,mod,posy,Y[ L[v] ],Y[ 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(Y , 0 , sizeof Y); // memset(L , 0 , sizeof L); // memset(R , 0 , sizeof R); id = 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 93 ms | 126072 KB | Output is correct |
2 | Correct | 94 ms | 126072 KB | Output is correct |
3 | Correct | 95 ms | 126072 KB | Output is correct |
4 | Correct | 92 ms | 125816 KB | Output is correct |
5 | Correct | 93 ms | 125924 KB | Output is correct |
6 | Correct | 94 ms | 125944 KB | Output is correct |
7 | Correct | 93 ms | 125944 KB | Output is correct |
8 | Correct | 93 ms | 125944 KB | Output is correct |
9 | Correct | 94 ms | 125984 KB | Output is correct |
10 | Correct | 96 ms | 126200 KB | Output is correct |
11 | Correct | 93 ms | 125912 KB | Output is correct |
12 | Correct | 92 ms | 125944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 96 ms | 125920 KB | Output is correct |
2 | Correct | 97 ms | 125816 KB | Output is correct |
3 | Correct | 98 ms | 125944 KB | Output is correct |
4 | Correct | 1275 ms | 145972 KB | Output is correct |
5 | Correct | 943 ms | 145520 KB | Output is correct |
6 | Correct | 1427 ms | 143196 KB | Output is correct |
7 | Correct | 1487 ms | 142976 KB | Output is correct |
8 | Correct | 921 ms | 138448 KB | Output is correct |
9 | Correct | 1430 ms | 143096 KB | Output is correct |
10 | Correct | 1298 ms | 142672 KB | Output is correct |
11 | Correct | 97 ms | 125944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 191 ms | 125816 KB | Output is correct |
2 | Correct | 100 ms | 126072 KB | Output is correct |
3 | Correct | 98 ms | 126072 KB | Output is correct |
4 | Correct | 98 ms | 125908 KB | Output is correct |
5 | Correct | 151 ms | 125944 KB | Output is correct |
6 | Correct | 95 ms | 126064 KB | Output is correct |
7 | Correct | 95 ms | 126020 KB | Output is correct |
8 | Correct | 96 ms | 125944 KB | Output is correct |
9 | Correct | 94 ms | 126072 KB | Output is correct |
10 | Correct | 96 ms | 125944 KB | Output is correct |
11 | Correct | 96 ms | 125880 KB | Output is correct |
12 | Correct | 1748 ms | 138568 KB | Output is correct |
13 | Correct | 2600 ms | 133600 KB | Output is correct |
14 | Correct | 721 ms | 131320 KB | Output is correct |
15 | Correct | 2974 ms | 135856 KB | Output is correct |
16 | Correct | 790 ms | 138744 KB | Output is correct |
17 | Correct | 2012 ms | 137592 KB | Output is correct |
18 | Correct | 3091 ms | 140136 KB | Output is correct |
19 | Correct | 2627 ms | 140332 KB | Output is correct |
20 | Correct | 2666 ms | 139612 KB | Output is correct |
21 | Correct | 94 ms | 125944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 94 ms | 125820 KB | Output is correct |
2 | Correct | 96 ms | 125992 KB | Output is correct |
3 | Correct | 94 ms | 125948 KB | Output is correct |
4 | Correct | 94 ms | 125916 KB | Output is correct |
5 | Correct | 92 ms | 125816 KB | Output is correct |
6 | Correct | 93 ms | 126088 KB | Output is correct |
7 | Correct | 94 ms | 125992 KB | Output is correct |
8 | Correct | 93 ms | 125932 KB | Output is correct |
9 | Correct | 93 ms | 125944 KB | Output is correct |
10 | Correct | 93 ms | 125944 KB | Output is correct |
11 | Correct | 93 ms | 125944 KB | Output is correct |
12 | Correct | 1213 ms | 145840 KB | Output is correct |
13 | Correct | 942 ms | 145656 KB | Output is correct |
14 | Correct | 1359 ms | 143188 KB | Output is correct |
15 | Correct | 1453 ms | 142968 KB | Output is correct |
16 | Correct | 922 ms | 138488 KB | Output is correct |
17 | Correct | 1480 ms | 143080 KB | Output is correct |
18 | Correct | 1322 ms | 142592 KB | Output is correct |
19 | Correct | 1808 ms | 138816 KB | Output is correct |
20 | Correct | 2626 ms | 133388 KB | Output is correct |
21 | Correct | 730 ms | 131192 KB | Output is correct |
22 | Correct | 3005 ms | 135792 KB | Output is correct |
23 | Correct | 810 ms | 138664 KB | Output is correct |
24 | Correct | 1927 ms | 137648 KB | Output is correct |
25 | Correct | 3050 ms | 140120 KB | Output is correct |
26 | Correct | 2507 ms | 140320 KB | Output is correct |
27 | Correct | 2570 ms | 139536 KB | Output is correct |
28 | Correct | 1267 ms | 231040 KB | Output is correct |
29 | Correct | 3081 ms | 242700 KB | Output is correct |
30 | Correct | 7363 ms | 201776 KB | Output is correct |
31 | Correct | 6924 ms | 185384 KB | Output is correct |
32 | Correct | 826 ms | 135680 KB | Output is correct |
33 | Correct | 1044 ms | 136592 KB | Output is correct |
34 | Correct | 1676 ms | 236516 KB | Output is correct |
35 | Correct | 2456 ms | 188732 KB | Output is correct |
36 | Correct | 4800 ms | 240720 KB | Output is correct |
37 | Correct | 3897 ms | 240800 KB | Output is correct |
38 | Correct | 3868 ms | 240148 KB | Output is correct |
39 | Correct | 3125 ms | 216340 KB | Output is correct |
40 | Correct | 100 ms | 125836 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 125892 KB | Output is correct |
2 | Correct | 97 ms | 125996 KB | Output is correct |
3 | Correct | 96 ms | 126040 KB | Output is correct |
4 | Correct | 95 ms | 125944 KB | Output is correct |
5 | Correct | 94 ms | 125888 KB | Output is correct |
6 | Correct | 100 ms | 125956 KB | Output is correct |
7 | Correct | 93 ms | 125816 KB | Output is correct |
8 | Correct | 94 ms | 125896 KB | Output is correct |
9 | Correct | 94 ms | 126072 KB | Output is correct |
10 | Correct | 95 ms | 125968 KB | Output is correct |
11 | Correct | 94 ms | 125944 KB | Output is correct |
12 | Correct | 1199 ms | 145704 KB | Output is correct |
13 | Correct | 925 ms | 145520 KB | Output is correct |
14 | Correct | 1356 ms | 143068 KB | Output is correct |
15 | Correct | 1382 ms | 142780 KB | Output is correct |
16 | Correct | 890 ms | 138488 KB | Output is correct |
17 | Correct | 1431 ms | 142968 KB | Output is correct |
18 | Correct | 1304 ms | 142700 KB | Output is correct |
19 | Correct | 1913 ms | 138544 KB | Output is correct |
20 | Correct | 2558 ms | 133428 KB | Output is correct |
21 | Correct | 710 ms | 131120 KB | Output is correct |
22 | Correct | 2934 ms | 135632 KB | Output is correct |
23 | Correct | 749 ms | 138580 KB | Output is correct |
24 | Correct | 1825 ms | 137516 KB | Output is correct |
25 | Correct | 3216 ms | 139984 KB | Output is correct |
26 | Correct | 2745 ms | 140108 KB | Output is correct |
27 | Correct | 2470 ms | 139516 KB | Output is correct |
28 | Correct | 1284 ms | 230960 KB | Output is correct |
29 | Correct | 2951 ms | 242644 KB | Output is correct |
30 | Correct | 7487 ms | 201780 KB | Output is correct |
31 | Correct | 6742 ms | 185424 KB | Output is correct |
32 | Correct | 800 ms | 135672 KB | Output is correct |
33 | Correct | 1051 ms | 136552 KB | Output is correct |
34 | Correct | 1593 ms | 236396 KB | Output is correct |
35 | Correct | 2387 ms | 188900 KB | Output is correct |
36 | Correct | 4492 ms | 240716 KB | Output is correct |
37 | Correct | 3495 ms | 240624 KB | Output is correct |
38 | Correct | 3614 ms | 240136 KB | Output is correct |
39 | Runtime error | 963 ms | 256000 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
40 | Halted | 0 ms | 0 KB | - |