# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
121595 | 2019-06-26T20:16:33 Z | yusufake | Game (IOI13_game) | C++ | 7786 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 * 525; int Y[N],L[N],R[N],id=1; ll s[N]; // 0 is empty node // s[0] should be ineffective element // 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 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(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(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) {}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 640 KB | Output is correct |
3 | Correct | 4 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
4 | Correct | 1117 ms | 28956 KB | Output is correct |
5 | Correct | 829 ms | 29072 KB | Output is correct |
6 | Correct | 1310 ms | 26088 KB | Output is correct |
7 | Correct | 1288 ms | 25736 KB | Output is correct |
8 | Correct | 973 ms | 16928 KB | Output is correct |
9 | Correct | 1315 ms | 25964 KB | Output is correct |
10 | Correct | 1189 ms | 25636 KB | Output is correct |
11 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 512 KB | Output is correct |
3 | Correct | 4 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 384 KB | Output is correct |
12 | Correct | 1719 ms | 13932 KB | Output is correct |
13 | Correct | 2509 ms | 7404 KB | Output is correct |
14 | Correct | 620 ms | 2520 KB | Output is correct |
15 | Correct | 2889 ms | 10340 KB | Output is correct |
16 | Correct | 674 ms | 16004 KB | Output is correct |
17 | Correct | 1806 ms | 12280 KB | Output is correct |
18 | Correct | 3014 ms | 16224 KB | Output is correct |
19 | Correct | 2739 ms | 16560 KB | Output is correct |
20 | Correct | 2411 ms | 15720 KB | Output is correct |
21 | Correct | 9 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 640 KB | Output is correct |
3 | Correct | 4 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 640 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 384 KB | Output is correct |
12 | Correct | 1123 ms | 28764 KB | Output is correct |
13 | Correct | 831 ms | 28920 KB | Output is correct |
14 | Correct | 1231 ms | 25760 KB | Output is correct |
15 | Correct | 1321 ms | 25500 KB | Output is correct |
16 | Correct | 738 ms | 16632 KB | Output is correct |
17 | Correct | 1260 ms | 25876 KB | Output is correct |
18 | Correct | 1285 ms | 25336 KB | Output is correct |
19 | Correct | 1677 ms | 13948 KB | Output is correct |
20 | Correct | 2540 ms | 7368 KB | Output is correct |
21 | Correct | 616 ms | 2484 KB | Output is correct |
22 | Correct | 2878 ms | 10356 KB | Output is correct |
23 | Correct | 787 ms | 15864 KB | Output is correct |
24 | Correct | 1774 ms | 12092 KB | Output is correct |
25 | Correct | 2991 ms | 16056 KB | Output is correct |
26 | Correct | 2678 ms | 16440 KB | Output is correct |
27 | Correct | 2450 ms | 15596 KB | Output is correct |
28 | Correct | 1168 ms | 159116 KB | Output is correct |
29 | Correct | 2991 ms | 177124 KB | Output is correct |
30 | Correct | 7786 ms | 121136 KB | Output is correct |
31 | Correct | 7133 ms | 92964 KB | Output is correct |
32 | Correct | 679 ms | 2416 KB | Output is correct |
33 | Correct | 915 ms | 4188 KB | Output is correct |
34 | Correct | 1551 ms | 174272 KB | Output is correct |
35 | Correct | 2282 ms | 89292 KB | Output is correct |
36 | Correct | 4298 ms | 174676 KB | Output is correct |
37 | Correct | 3691 ms | 174920 KB | Output is correct |
38 | Correct | 3468 ms | 174076 KB | Output is correct |
39 | Correct | 2996 ms | 134396 KB | Output is correct |
40 | Correct | 3 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 640 KB | Output is correct |
3 | Correct | 4 ms | 512 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 640 KB | Output is correct |
7 | Correct | 2 ms | 384 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 3 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 384 KB | Output is correct |
12 | Correct | 1113 ms | 28696 KB | Output is correct |
13 | Correct | 853 ms | 28796 KB | Output is correct |
14 | Correct | 1268 ms | 25756 KB | Output is correct |
15 | Correct | 1245 ms | 25616 KB | Output is correct |
16 | Correct | 788 ms | 16760 KB | Output is correct |
17 | Correct | 1287 ms | 25836 KB | Output is correct |
18 | Correct | 1142 ms | 25280 KB | Output is correct |
19 | Correct | 1958 ms | 13952 KB | Output is correct |
20 | Correct | 2505 ms | 7392 KB | Output is correct |
21 | Correct | 623 ms | 2424 KB | Output is correct |
22 | Correct | 2872 ms | 10276 KB | Output is correct |
23 | Correct | 673 ms | 15780 KB | Output is correct |
24 | Correct | 1778 ms | 12088 KB | Output is correct |
25 | Correct | 2916 ms | 16208 KB | Output is correct |
26 | Correct | 2556 ms | 16292 KB | Output is correct |
27 | Correct | 2339 ms | 15776 KB | Output is correct |
28 | Correct | 1168 ms | 158836 KB | Output is correct |
29 | Correct | 2858 ms | 176696 KB | Output is correct |
30 | Correct | 7455 ms | 120800 KB | Output is correct |
31 | Correct | 6740 ms | 92492 KB | Output is correct |
32 | Correct | 694 ms | 2184 KB | Output is correct |
33 | Correct | 919 ms | 3832 KB | Output is correct |
34 | Correct | 1561 ms | 173764 KB | Output is correct |
35 | Correct | 2185 ms | 88800 KB | Output is correct |
36 | Correct | 4455 ms | 174076 KB | Output is correct |
37 | Correct | 3510 ms | 174028 KB | Output is correct |
38 | Correct | 3525 ms | 173680 KB | Output is correct |
39 | Runtime error | 3076 ms | 256000 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
40 | Halted | 0 ms | 0 KB | - |