# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
135507 |
2019-07-24T07:15:43 Z |
ksmzzang2003 |
Game (IOI13_game) |
C++17 |
|
8716 ms |
173244 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int R,C,Q;
struct node1d
{
ll val=0;
int pos = -1;
node1d *lc=nullptr,*rc=nullptr;
void update(int s,int e,int t,ll v)
{
if(e<t || t<s )
return ;
if(s==e)
{
val=v;
return;
}
int m = (s+e)/2;
if(pos>=0)
{
if(pos<=m)
{
lc = new node1d;
lc->pos=pos,lc->val=val;
}
else
{
rc = new node1d;
rc->pos=pos,rc->val=val;
}
pos=-1;
}
if(t<=m)
{
if(lc==nullptr)
{
lc = new node1d;
lc->pos = t,lc->val = v;
}
else
lc-> update(s,m,t,v);
}
else
{
if(rc==nullptr)
{
rc= new node1d;
rc->pos = t,rc->val = v;
}
else
rc->update(m+1,e,t,v);
}
val =0;
if(lc!=nullptr)
val = __gcd(val,lc->val);
if(rc!=nullptr)
val = __gcd(val,rc->val);
}
ll query(int s,int e,int ts,int te)
{
if(te<s || e<ts)
return 0;
if(ts<=s && e<=te)
return val;
if(pos>=0)
{
if(ts<=pos && pos <=te)
return val;
return 0;
}
int m =(s+e)/2;
ll ret=0;
if(lc!=nullptr)
ret = __gcd(ret,lc->query(s,m,ts,te));
if(rc!=nullptr)
ret = __gcd(ret,rc->query(m+1,e,ts,te));
return ret;
}
};
struct node2d
{
node1d *T = new node1d;
node2d *lc=nullptr,*rc=nullptr;
void update(int s,int e,int tx,int ty,ll v)
{
if(e<tx || tx<s)
return ;
if(s==e)
{
T->update(0,C-1,ty,v);
return ;
}
int m = (s+e)/2;
if(tx<=m)
{
if(lc==nullptr)
lc = new node2d;
lc->update(s,m,tx,ty,v);
}
else
{
if(rc==nullptr)
rc = new node2d;
rc->update(m+1,e,tx,ty,v);
}
ll ret=0;
if(lc!=nullptr)
ret = __gcd(ret,lc->T->query(0,C-1,ty,ty));
if(rc!=nullptr)
ret = __gcd(ret,rc->T->query(0,C-1,ty,ty));
T->update(0,C-1,ty,ret);
}
ll query(int s,int e,int txs,int txe,int tys,int tye)
{
if(txe<s || e<txs)
return 0;
if(txs<=s && e<=txe)
return T->query(0,C-1,tys,tye);
int m = (s+e)/2;
ll ret=0;
if(lc!=nullptr)
ret = __gcd(ret,lc->query(s,m,txs,txe,tys,tye));
if(rc!=nullptr)
ret = __gcd(ret,rc->query(m+1,e,txs,txe,tys,tye));
return ret;
}
}*Seg = new node2d;
void init (int r,int c)
{
R=r,C=c;
}
void update(int x,int y,ll v)
{
Seg->update(0,R-1,x,y,v);
}
ll calculate(int x1,int y1,int x2,int y2)
{
return Seg->query(0,R-1,x1,x2,y1,y2);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
833 ms |
13732 KB |
Output is correct |
5 |
Correct |
602 ms |
13596 KB |
Output is correct |
6 |
Correct |
723 ms |
11180 KB |
Output is correct |
7 |
Correct |
808 ms |
10744 KB |
Output is correct |
8 |
Correct |
503 ms |
8572 KB |
Output is correct |
9 |
Correct |
791 ms |
10960 KB |
Output is correct |
10 |
Correct |
702 ms |
10476 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
380 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
252 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
1492 ms |
17112 KB |
Output is correct |
13 |
Correct |
2748 ms |
10736 KB |
Output is correct |
14 |
Correct |
411 ms |
5780 KB |
Output is correct |
15 |
Correct |
3225 ms |
13540 KB |
Output is correct |
16 |
Correct |
286 ms |
15864 KB |
Output is correct |
17 |
Correct |
1243 ms |
12004 KB |
Output is correct |
18 |
Correct |
2234 ms |
17408 KB |
Output is correct |
19 |
Correct |
1868 ms |
17508 KB |
Output is correct |
20 |
Correct |
1693 ms |
17080 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
380 KB |
Output is correct |
12 |
Correct |
863 ms |
13804 KB |
Output is correct |
13 |
Correct |
638 ms |
13432 KB |
Output is correct |
14 |
Correct |
724 ms |
11128 KB |
Output is correct |
15 |
Correct |
827 ms |
10816 KB |
Output is correct |
16 |
Correct |
507 ms |
8620 KB |
Output is correct |
17 |
Correct |
858 ms |
10844 KB |
Output is correct |
18 |
Correct |
714 ms |
10660 KB |
Output is correct |
19 |
Correct |
1487 ms |
17032 KB |
Output is correct |
20 |
Correct |
2750 ms |
10812 KB |
Output is correct |
21 |
Correct |
406 ms |
5792 KB |
Output is correct |
22 |
Correct |
3202 ms |
13520 KB |
Output is correct |
23 |
Correct |
287 ms |
16000 KB |
Output is correct |
24 |
Correct |
1186 ms |
12284 KB |
Output is correct |
25 |
Correct |
2419 ms |
17512 KB |
Output is correct |
26 |
Correct |
1836 ms |
17440 KB |
Output is correct |
27 |
Correct |
1688 ms |
16908 KB |
Output is correct |
28 |
Correct |
823 ms |
55928 KB |
Output is correct |
29 |
Correct |
2124 ms |
51264 KB |
Output is correct |
30 |
Correct |
6857 ms |
48240 KB |
Output is correct |
31 |
Correct |
6446 ms |
87352 KB |
Output is correct |
32 |
Correct |
903 ms |
10692 KB |
Output is correct |
33 |
Correct |
1230 ms |
14440 KB |
Output is correct |
34 |
Correct |
400 ms |
44792 KB |
Output is correct |
35 |
Correct |
1631 ms |
29724 KB |
Output is correct |
36 |
Correct |
3020 ms |
48948 KB |
Output is correct |
37 |
Correct |
2580 ms |
49220 KB |
Output is correct |
38 |
Correct |
2378 ms |
48716 KB |
Output is correct |
39 |
Correct |
2283 ms |
40304 KB |
Output is correct |
40 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
831 ms |
13860 KB |
Output is correct |
13 |
Correct |
591 ms |
13560 KB |
Output is correct |
14 |
Correct |
780 ms |
11156 KB |
Output is correct |
15 |
Correct |
797 ms |
10760 KB |
Output is correct |
16 |
Correct |
507 ms |
8684 KB |
Output is correct |
17 |
Correct |
760 ms |
10872 KB |
Output is correct |
18 |
Correct |
693 ms |
10404 KB |
Output is correct |
19 |
Correct |
1447 ms |
16988 KB |
Output is correct |
20 |
Correct |
2776 ms |
10816 KB |
Output is correct |
21 |
Correct |
403 ms |
5752 KB |
Output is correct |
22 |
Correct |
3214 ms |
13620 KB |
Output is correct |
23 |
Correct |
288 ms |
15864 KB |
Output is correct |
24 |
Correct |
1197 ms |
12108 KB |
Output is correct |
25 |
Correct |
2122 ms |
17440 KB |
Output is correct |
26 |
Correct |
1902 ms |
17784 KB |
Output is correct |
27 |
Correct |
1946 ms |
16876 KB |
Output is correct |
28 |
Correct |
831 ms |
55808 KB |
Output is correct |
29 |
Correct |
2163 ms |
51084 KB |
Output is correct |
30 |
Correct |
6811 ms |
48044 KB |
Output is correct |
31 |
Correct |
6402 ms |
87416 KB |
Output is correct |
32 |
Correct |
920 ms |
10820 KB |
Output is correct |
33 |
Correct |
1211 ms |
14740 KB |
Output is correct |
34 |
Correct |
414 ms |
44796 KB |
Output is correct |
35 |
Correct |
1570 ms |
29688 KB |
Output is correct |
36 |
Correct |
3049 ms |
49000 KB |
Output is correct |
37 |
Correct |
2415 ms |
49220 KB |
Output is correct |
38 |
Correct |
2435 ms |
48732 KB |
Output is correct |
39 |
Correct |
1119 ms |
110940 KB |
Output is correct |
40 |
Correct |
3311 ms |
94796 KB |
Output is correct |
41 |
Correct |
8716 ms |
95340 KB |
Output is correct |
42 |
Correct |
8641 ms |
173244 KB |
Output is correct |
43 |
Correct |
899 ms |
89432 KB |
Output is correct |
44 |
Correct |
1379 ms |
11104 KB |
Output is correct |
45 |
Correct |
2200 ms |
40120 KB |
Output is correct |
46 |
Correct |
3885 ms |
93496 KB |
Output is correct |
47 |
Correct |
3875 ms |
93640 KB |
Output is correct |
48 |
Correct |
3980 ms |
93112 KB |
Output is correct |
49 |
Correct |
2 ms |
256 KB |
Output is correct |