# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
250333 |
2020-07-17T12:27:19 Z |
MarcoMeijer |
Game (IOI13_game) |
C++14 |
|
4352 ms |
105208 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
int R, C;
ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Seg {
int bg, ed;
ll val;
Seg* ls=nullptr;
Seg* rs=nullptr;
Seg(int l, int r, ll v=0) {
bg=l; ed=r; val=v;
}
ll f(Seg* s) {
if(s == nullptr) return 0;
return s->val;
}
ll f(Seg* s, int i, int j, int l, int r) {
if(s == nullptr) return 0;
return s->get(i,j,l,r);
}
void set(int i, ll v, int l, int r) {
int m=(l+r)/2;
if(bg == ed) {
if(i == bg) {
val = v;
return;
} else {
int j = bg;
bg = l; ed = r;
if(j <= m) {
ls = new Seg(j,j,val);
} else {
rs = new Seg(j,j,val);
}
}
}
if(i <= m) {
if(ls == nullptr) ls = new Seg(i,i);
ls->set(i,v,l,m);
} else {
if(rs == nullptr) rs = new Seg(i,i);
rs->set(i,v,m+1,r);
}
val = gcd(f(ls), f(rs));
}
ll get(int i, int j, int l, int r) {
if(j < bg || i > ed) return 0;
if(i <= bg && j >= ed) return val;
int m=(l+r)/2;
ll a = f(ls,i,j,l,m);
ll b = f(rs,i,j,m+1,r);
return gcd(a,b);
}
};
struct Seg2 {
int bg, ed;
Seg val;
Seg2* ls=nullptr;
Seg2* rs=nullptr;
Seg2(int l, int r) : val(0,C-1) {
bg = l; ed = r;
}
ll f(Seg2* s, int j) {
if(s == nullptr) return 0;
return s->val.get(j,j,0,C-1);
}
void set(int i, int j, ll v, int l, int r) {
int m=(l+r)/2;
if(l == r) {
val.set(j,v,0,C-1);
return;
}
if(i <= m) {
if(ls == nullptr) ls = new Seg2(l,m);
ls->set(i,j,v,l,m);
} else {
if(rs == nullptr) rs = new Seg2(m+1,r);
rs->set(i,j,v,m+1,r);
}
ll nV = 0;
nV = gcd(f(ls,j), f(rs,j));
val.set(j,nV,0,C-1);
}
ll f(Seg2* s, int i, int j, int I, int J, int l, int r) {
if(s == nullptr) return 0;
return s->get(i,j,I,J,l,r);
}
ll get(int i, int j, int I, int J, int l, int r) {
if(j < l || i > r) return 0;
if(i <= l && j >= r) return val.get(I,J,0,C-1);
int m=(l+r)/2;
ll a = f(ls,i,j,I,J,l,m);
ll b = f(rs,i,j,I,J,m+1,r);
return gcd(a,b);
}
};
Seg2* SEG;
void init(int _R, int _C) {
R = _R;
C = _C;
SEG = new Seg2(0,R-1);
//RE(i,R) SEG[i] = new Seg(0,C-1);
}
void update(int P, int Q, ll K) {
SEG->set(P,Q,K,0,R-1);
//SEG[P]->set(Q,K,0,C-1);
}
ll calculate(int P, int Q, int U, int V) {
/*ll ans = 0;
REP(i,P,U+1) ans = gcd(ans, SEG[i]->get(Q,V,0,C-1));
return ans;*/
return SEG->get(P,U,Q,V,0,R-1);
}
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 |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
573 ms |
9192 KB |
Output is correct |
5 |
Correct |
380 ms |
9392 KB |
Output is correct |
6 |
Correct |
546 ms |
6264 KB |
Output is correct |
7 |
Correct |
580 ms |
5924 KB |
Output is correct |
8 |
Correct |
427 ms |
4428 KB |
Output is correct |
9 |
Correct |
598 ms |
6008 KB |
Output is correct |
10 |
Correct |
531 ms |
5752 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
830 ms |
12664 KB |
Output is correct |
13 |
Correct |
1414 ms |
6016 KB |
Output is correct |
14 |
Correct |
320 ms |
1144 KB |
Output is correct |
15 |
Correct |
1637 ms |
7692 KB |
Output is correct |
16 |
Correct |
248 ms |
11256 KB |
Output is correct |
17 |
Correct |
787 ms |
7032 KB |
Output is correct |
18 |
Correct |
1444 ms |
11864 KB |
Output is correct |
19 |
Correct |
1183 ms |
12152 KB |
Output is correct |
20 |
Correct |
1328 ms |
11384 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
572 ms |
9144 KB |
Output is correct |
13 |
Correct |
361 ms |
9464 KB |
Output is correct |
14 |
Correct |
543 ms |
6264 KB |
Output is correct |
15 |
Correct |
606 ms |
6008 KB |
Output is correct |
16 |
Correct |
418 ms |
4328 KB |
Output is correct |
17 |
Correct |
636 ms |
6264 KB |
Output is correct |
18 |
Correct |
525 ms |
5752 KB |
Output is correct |
19 |
Correct |
815 ms |
12408 KB |
Output is correct |
20 |
Correct |
1427 ms |
5880 KB |
Output is correct |
21 |
Correct |
315 ms |
1212 KB |
Output is correct |
22 |
Correct |
1637 ms |
7696 KB |
Output is correct |
23 |
Correct |
233 ms |
11256 KB |
Output is correct |
24 |
Correct |
822 ms |
7032 KB |
Output is correct |
25 |
Correct |
1389 ms |
11848 KB |
Output is correct |
26 |
Correct |
1208 ms |
11768 KB |
Output is correct |
27 |
Correct |
1109 ms |
11300 KB |
Output is correct |
28 |
Correct |
686 ms |
53312 KB |
Output is correct |
29 |
Correct |
1405 ms |
48424 KB |
Output is correct |
30 |
Correct |
3278 ms |
46532 KB |
Output is correct |
31 |
Correct |
2985 ms |
37092 KB |
Output is correct |
32 |
Correct |
537 ms |
10744 KB |
Output is correct |
33 |
Correct |
781 ms |
14328 KB |
Output is correct |
34 |
Correct |
323 ms |
42232 KB |
Output is correct |
35 |
Correct |
1108 ms |
28536 KB |
Output is correct |
36 |
Correct |
2142 ms |
46340 KB |
Output is correct |
37 |
Correct |
1656 ms |
46416 KB |
Output is correct |
38 |
Correct |
1593 ms |
46200 KB |
Output is correct |
39 |
Correct |
1329 ms |
38008 KB |
Output is correct |
40 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
545 ms |
9084 KB |
Output is correct |
13 |
Correct |
359 ms |
9592 KB |
Output is correct |
14 |
Correct |
565 ms |
6304 KB |
Output is correct |
15 |
Correct |
638 ms |
6020 KB |
Output is correct |
16 |
Correct |
401 ms |
4344 KB |
Output is correct |
17 |
Correct |
561 ms |
6012 KB |
Output is correct |
18 |
Correct |
523 ms |
5752 KB |
Output is correct |
19 |
Correct |
838 ms |
12436 KB |
Output is correct |
20 |
Correct |
1399 ms |
6008 KB |
Output is correct |
21 |
Correct |
315 ms |
1052 KB |
Output is correct |
22 |
Correct |
1677 ms |
7640 KB |
Output is correct |
23 |
Correct |
243 ms |
11256 KB |
Output is correct |
24 |
Correct |
790 ms |
6916 KB |
Output is correct |
25 |
Correct |
1514 ms |
11996 KB |
Output is correct |
26 |
Correct |
1154 ms |
11768 KB |
Output is correct |
27 |
Correct |
1133 ms |
11204 KB |
Output is correct |
28 |
Correct |
650 ms |
53240 KB |
Output is correct |
29 |
Correct |
1434 ms |
48584 KB |
Output is correct |
30 |
Correct |
3274 ms |
46332 KB |
Output is correct |
31 |
Correct |
2972 ms |
37088 KB |
Output is correct |
32 |
Correct |
542 ms |
10872 KB |
Output is correct |
33 |
Correct |
781 ms |
14200 KB |
Output is correct |
34 |
Correct |
330 ms |
42144 KB |
Output is correct |
35 |
Correct |
1191 ms |
28416 KB |
Output is correct |
36 |
Correct |
1994 ms |
46348 KB |
Output is correct |
37 |
Correct |
1650 ms |
46708 KB |
Output is correct |
38 |
Correct |
1648 ms |
46200 KB |
Output is correct |
39 |
Correct |
992 ms |
105208 KB |
Output is correct |
40 |
Correct |
2150 ms |
88844 KB |
Output is correct |
41 |
Correct |
4352 ms |
91852 KB |
Output is correct |
42 |
Correct |
3925 ms |
70992 KB |
Output is correct |
43 |
Correct |
514 ms |
83704 KB |
Output is correct |
44 |
Correct |
724 ms |
11080 KB |
Output is correct |
45 |
Correct |
1421 ms |
38024 KB |
Output is correct |
46 |
Correct |
2737 ms |
87932 KB |
Output is correct |
47 |
Correct |
2795 ms |
87980 KB |
Output is correct |
48 |
Correct |
2536 ms |
87408 KB |
Output is correct |
49 |
Correct |
0 ms |
256 KB |
Output is correct |