# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
94592 |
2019-01-21T12:12:23 Z |
Retro3014 |
Game (IOI13_game) |
C++17 |
|
6801 ms |
257024 KB |
#include "game.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <deque>
typedef long long ll;
using namespace std;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SEG2{
int s, e;
int l=-1, r=-1;
ll gcd = 0;
};
vector<SEG2> s2;
struct SEG1{
int s, e;
int l, r;
vector<SEG2> seg2;
};
vector<SEG1> seg1;
int r, c;
void init(int R, int C) {
r = R; c = C;
seg1.push_back({0, R-1, -1, -1, s2});
}
int qq;
ll k;
void update2(int x, int y){
//seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[y].gcd, K);
if(seg1[x].seg2[y].s==seg1[x].seg2[y].e){
seg1[x].seg2[y].gcd = k;
return;
}
if(qq<=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2){
if(seg1[x].seg2[y].l==-1){
seg1[x].seg2[y].l = seg1[x].seg2.size();
SEG2 tmp; tmp.s=seg1[x].seg2[y].s; tmp.e=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2; tmp.l=-1;tmp.r=-1;tmp.gcd=0;
seg1[x].seg2.push_back(tmp);
}
update2(x, seg1[x].seg2[y].l);
if(seg1[x].seg2[y].r==-1) seg1[x].seg2[y].gcd = seg1[x].seg2[seg1[x].seg2[y].l].gcd;
else seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[seg1[x].seg2[y].l].gcd, seg1[x].seg2[seg1[x].seg2[y].r].gcd);
}else{
if(seg1[x].seg2[y].r==-1){
seg1[x].seg2[y].r = seg1[x].seg2.size();
SEG2 tmp; tmp.s=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2+1; tmp.e=seg1[x].seg2[y].e; tmp.l=-1;tmp.r=-1;tmp.gcd=0;
seg1[x].seg2.push_back(tmp);
}
update2(x, seg1[x].seg2[y].r);
if(seg1[x].seg2[y].l==-1) seg1[x].seg2[y].gcd = seg1[x].seg2[seg1[x].seg2[y].r].gcd;
else seg1[x].seg2[y].gcd = gcd2(seg1[x].seg2[seg1[x].seg2[y].l].gcd, seg1[x].seg2[seg1[x].seg2[y].r].gcd);
}
}
int pp;
ll findg(int x, int y){
if(y==-1) return 0;
if(seg1[x].seg2[y].s==seg1[x].seg2[y].e) return seg1[x].seg2[y].gcd;
if(qq<=(seg1[x].seg2[y].s+seg1[x].seg2[y].e)/2) return findg(x, seg1[x].seg2[y].l);
else return findg(x, seg1[x].seg2[y].r);
}
void update1(int x){
if(seg1[x].seg2.empty()){
SEG2 tmp;tmp.s=0;tmp.e=c-1;tmp.l=-1;tmp.r=-1;tmp.gcd=0;
seg1[x].seg2.push_back(tmp);
}
if(seg1[x].s==seg1[x].e){
update2(x, 0); return;
}
if(pp<=(seg1[x].s+seg1[x].e)/2){
if(seg1[x].l==-1){
seg1[x].l = seg1.size();
seg1.push_back({seg1[x].s, (seg1[x].s+seg1[x].e)/2, -1, -1, s2});
}
update1(seg1[x].l);
if(seg1[x].r!=-1 && !seg1[seg1[x].r].seg2.empty()) k = gcd2(k, findg(seg1[x].r, 0));
}else{
if(seg1[x].r==-1){
seg1[x].r = seg1.size();
seg1.push_back({(seg1[x].s+seg1[x].e)/2+1, seg1[x].e, -1, -1, s2});
}
update1(seg1[x].r);
if(seg1[x].l!=-1 && !seg1[seg1[x].l].seg2.empty()) k = gcd2(k, findg(seg1[x].l, 0));
}
update2(x, 0);
}
void update(int P, int Q, long long K) {
pp = P; qq = Q; k = K;
update1(0);
}
int p, q, u, v;
ll calc2(int x, int y){
if(y==-1) return 0;
if(seg1[x].seg2[y].s > v || seg1[x].seg2[y].e < q) return 0;
if(q <= seg1[x].seg2[y].s && seg1[x].seg2[y].e <= v) return seg1[x].seg2[y].gcd;
return gcd2(calc2(x, seg1[x].seg2[y].l), calc2(x, seg1[x].seg2[y].r));
}
ll calc1(int x){
if(x==-1) return 0;
if(seg1[x].s>u || seg1[x].e<p) return 0;
if(p <= seg1[x].s && seg1[x].e <= u){
if(seg1[x].seg2.empty()) return 0;
else{
return calc2(x, 0);
}
}
return gcd2(calc1(seg1[x].l), calc1(seg1[x].r));
}
long long calculate(int P, int Q, int U, int V) {
p = P; q = Q;
u = U; v = V;
return calc1(0);
}
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 |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
252 KB |
Output is correct |
9 |
Correct |
2 ms |
504 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 |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
695 ms |
16924 KB |
Output is correct |
5 |
Correct |
430 ms |
16856 KB |
Output is correct |
6 |
Correct |
740 ms |
13948 KB |
Output is correct |
7 |
Correct |
814 ms |
14136 KB |
Output is correct |
8 |
Correct |
532 ms |
11004 KB |
Output is correct |
9 |
Correct |
770 ms |
14360 KB |
Output is correct |
10 |
Correct |
629 ms |
13236 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
256 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 |
1149 ms |
20588 KB |
Output is correct |
13 |
Correct |
2402 ms |
10292 KB |
Output is correct |
14 |
Correct |
352 ms |
5776 KB |
Output is correct |
15 |
Correct |
2862 ms |
13352 KB |
Output is correct |
16 |
Correct |
278 ms |
23568 KB |
Output is correct |
17 |
Correct |
1235 ms |
16996 KB |
Output is correct |
18 |
Correct |
2197 ms |
25284 KB |
Output is correct |
19 |
Correct |
1821 ms |
25156 KB |
Output is correct |
20 |
Correct |
1819 ms |
24412 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
12 |
Correct |
715 ms |
17232 KB |
Output is correct |
13 |
Correct |
430 ms |
17004 KB |
Output is correct |
14 |
Correct |
726 ms |
14104 KB |
Output is correct |
15 |
Correct |
826 ms |
14176 KB |
Output is correct |
16 |
Correct |
516 ms |
10940 KB |
Output is correct |
17 |
Correct |
794 ms |
14292 KB |
Output is correct |
18 |
Correct |
699 ms |
13352 KB |
Output is correct |
19 |
Correct |
1119 ms |
20796 KB |
Output is correct |
20 |
Correct |
2374 ms |
10276 KB |
Output is correct |
21 |
Correct |
343 ms |
5716 KB |
Output is correct |
22 |
Correct |
2783 ms |
13388 KB |
Output is correct |
23 |
Correct |
238 ms |
23416 KB |
Output is correct |
24 |
Correct |
1160 ms |
17032 KB |
Output is correct |
25 |
Correct |
1989 ms |
25044 KB |
Output is correct |
26 |
Correct |
1669 ms |
25228 KB |
Output is correct |
27 |
Correct |
1751 ms |
24436 KB |
Output is correct |
28 |
Correct |
997 ms |
226072 KB |
Output is correct |
29 |
Correct |
2248 ms |
247940 KB |
Output is correct |
30 |
Correct |
6704 ms |
180644 KB |
Output is correct |
31 |
Correct |
6400 ms |
147160 KB |
Output is correct |
32 |
Correct |
639 ms |
10500 KB |
Output is correct |
33 |
Correct |
912 ms |
13968 KB |
Output is correct |
34 |
Correct |
841 ms |
242116 KB |
Output is correct |
35 |
Correct |
2021 ms |
129276 KB |
Output is correct |
36 |
Correct |
3629 ms |
246048 KB |
Output is correct |
37 |
Correct |
3368 ms |
246268 KB |
Output is correct |
38 |
Correct |
3394 ms |
245740 KB |
Output is correct |
39 |
Correct |
2654 ms |
191952 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 |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
12 |
Correct |
718 ms |
16956 KB |
Output is correct |
13 |
Correct |
434 ms |
16896 KB |
Output is correct |
14 |
Correct |
715 ms |
13980 KB |
Output is correct |
15 |
Correct |
864 ms |
14012 KB |
Output is correct |
16 |
Correct |
524 ms |
10888 KB |
Output is correct |
17 |
Correct |
807 ms |
14464 KB |
Output is correct |
18 |
Correct |
670 ms |
13340 KB |
Output is correct |
19 |
Correct |
1094 ms |
20836 KB |
Output is correct |
20 |
Correct |
2420 ms |
10332 KB |
Output is correct |
21 |
Correct |
340 ms |
5752 KB |
Output is correct |
22 |
Correct |
2794 ms |
13480 KB |
Output is correct |
23 |
Correct |
251 ms |
23416 KB |
Output is correct |
24 |
Correct |
1295 ms |
16924 KB |
Output is correct |
25 |
Correct |
2011 ms |
25156 KB |
Output is correct |
26 |
Correct |
2035 ms |
25164 KB |
Output is correct |
27 |
Correct |
1491 ms |
24296 KB |
Output is correct |
28 |
Correct |
1175 ms |
226448 KB |
Output is correct |
29 |
Correct |
2574 ms |
247876 KB |
Output is correct |
30 |
Correct |
6801 ms |
180544 KB |
Output is correct |
31 |
Correct |
6442 ms |
147040 KB |
Output is correct |
32 |
Correct |
658 ms |
10664 KB |
Output is correct |
33 |
Correct |
953 ms |
14216 KB |
Output is correct |
34 |
Correct |
825 ms |
242080 KB |
Output is correct |
35 |
Correct |
2202 ms |
129164 KB |
Output is correct |
36 |
Correct |
4025 ms |
246048 KB |
Output is correct |
37 |
Correct |
2858 ms |
245932 KB |
Output is correct |
38 |
Correct |
3416 ms |
245748 KB |
Output is correct |
39 |
Runtime error |
796 ms |
257024 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
40 |
Halted |
0 ms |
0 KB |
- |