# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
471281 |
2021-09-08T06:31:37 Z |
CSQ31 |
게임 (IOI13_game) |
C++17 |
|
3352 ms |
72732 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int r,c;
ll gcd2(ll a,ll b){if(!b)return a;else if(!a)return b;else return gcd2(b,a%b);}
struct node{
node *L = NULL,*R = NULL;
int l,r;
ll val = 0;
node(){}
node(int _l,int _r):l(_l),r(_r){}
void upd(int x,ll v){
if(l == r){val = v;return;}
int mid = (l+r)/2;
node *& tp = (x<=mid?L : R);
if(tp == NULL){
tp = new node(x,x);
tp->val = v;
}else if(tp->l<=x && x<=tp->r)tp->upd(x,v);
else{
//we want to find the ancestor of this node and x
int low = l;
int high = r;
while((x<=mid) == (tp->l <= mid)){
if(x<=mid)high = mid;
else low = mid+1;
mid = (high+low)/2;
}
node * nn = new node(low,high);
//we want to replace tp with nn then attach back the original shit as nn's child
(tp->l<=mid?nn->L : nn->R) = tp;
tp = nn;
nn->upd(x,v);
}
val = gcd2(L==NULL?0:L->val,R == NULL?0:R->val);
}
ll query(int tl,int tr){
if(tl<=l && r<=tr)return val;
if(l > tr || tl > r)return 0;
return gcd2(L?L->query(tl,tr):0 , R?R->query(tl,tr):0);
}
};
struct nodex{
nodex *L = NULL,*R = NULL;
node tree;
ll val = 0;
nodex(){tree = node(1,c);}
}*root;
void upd(nodex *v,int x,int y,int l,int r,ll val){
if(l==r){
v->tree.upd(y,val);
return;
}
else{
int tm =(l+r)/2;
if(x<=tm){
if(v->L == NULL)v->L = new nodex();
upd(v->L,x,y,l,tm,val);
}else{
if(v->R == NULL)v->R = new nodex();
upd(v->R,x,y,tm+1,r,val);
}
}
ll k = gcd2(v->L == NULL?0:v->L->tree.query(y,y) ,
v->R == NULL?0:v->R->tree.query(y,y));
v->tree.upd(y,k);
}
ll query(nodex *v,int xl,int xr,int yl,int yr,int l,int r){
if(xl == l && xr == r){
return v->tree.query(yl,yr);
}
ll res = 0;
int tm = (l+r)/2;
if(xl<=tm && v->L != NULL)res = gcd2(query(v->L,xl,min(tm,xr),yl,yr,l,tm),res);
if(xr> tm && v->R != NULL)res = gcd2(query(v->R,max(xl,tm+1),xr,yl,yr,tm+1,r),res);
return res;
}
void init(int R, int C) {
r=R+1;
c=C+1;
root = new nodex();
}
void update(int P, int Q, ll K) {
P++;
Q++;
upd(root,P,Q,1,r,K);
}
long long calculate(int P, int Q, int U, int V) {
P++;
Q++;
U++;
V++;
return query(root,P,U,Q,V,1,r);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
499 ms |
10596 KB |
Output is correct |
5 |
Correct |
352 ms |
10904 KB |
Output is correct |
6 |
Correct |
471 ms |
7620 KB |
Output is correct |
7 |
Correct |
530 ms |
7348 KB |
Output is correct |
8 |
Correct |
357 ms |
6084 KB |
Output is correct |
9 |
Correct |
582 ms |
7372 KB |
Output is correct |
10 |
Correct |
467 ms |
6980 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
878 ms |
13512 KB |
Output is correct |
13 |
Correct |
1605 ms |
7004 KB |
Output is correct |
14 |
Correct |
254 ms |
3112 KB |
Output is correct |
15 |
Correct |
1766 ms |
8348 KB |
Output is correct |
16 |
Correct |
646 ms |
11844 KB |
Output is correct |
17 |
Correct |
690 ms |
8236 KB |
Output is correct |
18 |
Correct |
1265 ms |
12444 KB |
Output is correct |
19 |
Correct |
1068 ms |
12360 KB |
Output is correct |
20 |
Correct |
958 ms |
11872 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
483 ms |
10540 KB |
Output is correct |
13 |
Correct |
366 ms |
10824 KB |
Output is correct |
14 |
Correct |
483 ms |
7620 KB |
Output is correct |
15 |
Correct |
534 ms |
7460 KB |
Output is correct |
16 |
Correct |
355 ms |
5880 KB |
Output is correct |
17 |
Correct |
520 ms |
7500 KB |
Output is correct |
18 |
Correct |
540 ms |
7108 KB |
Output is correct |
19 |
Correct |
863 ms |
13636 KB |
Output is correct |
20 |
Correct |
1542 ms |
7008 KB |
Output is correct |
21 |
Correct |
250 ms |
2948 KB |
Output is correct |
22 |
Correct |
1781 ms |
8212 KB |
Output is correct |
23 |
Correct |
665 ms |
11844 KB |
Output is correct |
24 |
Correct |
681 ms |
8308 KB |
Output is correct |
25 |
Correct |
1266 ms |
12400 KB |
Output is correct |
26 |
Correct |
1036 ms |
12408 KB |
Output is correct |
27 |
Correct |
1006 ms |
11848 KB |
Output is correct |
28 |
Correct |
458 ms |
34640 KB |
Output is correct |
29 |
Correct |
1288 ms |
37456 KB |
Output is correct |
30 |
Correct |
2432 ms |
30328 KB |
Output is correct |
31 |
Correct |
2194 ms |
23596 KB |
Output is correct |
32 |
Correct |
367 ms |
2988 KB |
Output is correct |
33 |
Correct |
499 ms |
3708 KB |
Output is correct |
34 |
Correct |
782 ms |
34400 KB |
Output is correct |
35 |
Correct |
930 ms |
19088 KB |
Output is correct |
36 |
Correct |
1846 ms |
34600 KB |
Output is correct |
37 |
Correct |
1537 ms |
34888 KB |
Output is correct |
38 |
Correct |
1501 ms |
34028 KB |
Output is correct |
39 |
Correct |
1236 ms |
27224 KB |
Output is correct |
40 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
488 ms |
10240 KB |
Output is correct |
13 |
Correct |
358 ms |
10604 KB |
Output is correct |
14 |
Correct |
486 ms |
7404 KB |
Output is correct |
15 |
Correct |
540 ms |
7088 KB |
Output is correct |
16 |
Correct |
361 ms |
5836 KB |
Output is correct |
17 |
Correct |
519 ms |
7152 KB |
Output is correct |
18 |
Correct |
490 ms |
6768 KB |
Output is correct |
19 |
Correct |
876 ms |
13416 KB |
Output is correct |
20 |
Correct |
1583 ms |
6752 KB |
Output is correct |
21 |
Correct |
251 ms |
2708 KB |
Output is correct |
22 |
Correct |
1762 ms |
7872 KB |
Output is correct |
23 |
Correct |
639 ms |
11644 KB |
Output is correct |
24 |
Correct |
742 ms |
8028 KB |
Output is correct |
25 |
Correct |
1425 ms |
11876 KB |
Output is correct |
26 |
Correct |
1151 ms |
12092 KB |
Output is correct |
27 |
Correct |
1096 ms |
11564 KB |
Output is correct |
28 |
Correct |
483 ms |
34124 KB |
Output is correct |
29 |
Correct |
1325 ms |
36988 KB |
Output is correct |
30 |
Correct |
2414 ms |
30088 KB |
Output is correct |
31 |
Correct |
2230 ms |
23188 KB |
Output is correct |
32 |
Correct |
370 ms |
2636 KB |
Output is correct |
33 |
Correct |
503 ms |
3140 KB |
Output is correct |
34 |
Correct |
793 ms |
33800 KB |
Output is correct |
35 |
Correct |
922 ms |
18596 KB |
Output is correct |
36 |
Correct |
1897 ms |
33960 KB |
Output is correct |
37 |
Correct |
1511 ms |
34444 KB |
Output is correct |
38 |
Correct |
1422 ms |
33624 KB |
Output is correct |
39 |
Correct |
602 ms |
71364 KB |
Output is correct |
40 |
Correct |
2071 ms |
72732 KB |
Output is correct |
41 |
Correct |
3352 ms |
60860 KB |
Output is correct |
42 |
Correct |
3003 ms |
46224 KB |
Output is correct |
43 |
Correct |
1060 ms |
70544 KB |
Output is correct |
44 |
Correct |
439 ms |
2000 KB |
Output is correct |
45 |
Correct |
1281 ms |
26212 KB |
Output is correct |
46 |
Correct |
2703 ms |
70616 KB |
Output is correct |
47 |
Correct |
2534 ms |
70804 KB |
Output is correct |
48 |
Correct |
2514 ms |
70048 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |