# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
218667 |
2020-04-02T13:32:37 Z |
urd05 |
게임 (IOI13_game) |
C++14 |
|
4116 ms |
256000 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;
int r,c;
const int siz=1<<30;
long long gcd(long long a,long long b) {
if (b==0) {
return a;
}
return gcd(b,a%b);
}
struct Node {
long long val;
int lr;
};
Node seg[17000000];
int s=0;
int sz=0;
const long long INF=2e18;
int root[700000];
void init0(int node) {
root[node]=sz;
seg[sz++]={2*INF,-1};
}
void update0(int y,long long v,int node,int nodel=0,int noder=c-1) {
if (nodel==noder) {
seg[node].val=(seg[node].val/INF)*INF+v;
return;
}
int mid=(nodel+noder)/2;
if (y<=mid) {
if (seg[node].val/INF==0) {
update0(y,v,node+1,nodel,mid);
}
if (seg[node].val/INF==1) {
if (seg[node].lr==-1) {
seg[node].lr=sz;
seg[sz++]={2*INF,-1};
}
update0(y,v,seg[node].lr,nodel,mid);
}
if (seg[node].val/INF==2) {
seg[node].val-=2*INF;
seg[sz++]={2*INF,-1};
update0(y,v,node+1,nodel,mid);
}
}
else {
if (seg[node].val/INF==0) {
if (seg[node].lr==-1) {
seg[node].lr=sz;
seg[sz++]={2*INF,-1};
}
update0(y,v,seg[node].lr,mid+1,noder);
}
if (seg[node].val/INF==1) {
update0(y,v,node+1,mid+1,noder);
}
if (seg[node].val/INF==2) {
seg[node].val-=INF;
seg[sz++]={2*INF,-1};
update0(y,v,node+1,mid+1,noder);
}
}
long long x=0;
if (seg[node].val/INF==0) {
x=gcd(x,seg[node+1].val%INF);
}
else if (seg[node].lr!=-1) {
x=gcd(x,seg[seg[node].lr].val%INF);
}
if (seg[node].val/INF==1) {
x=gcd(x,seg[node+1].val%INF);
}
else if (seg[node].lr!=-1) {
x=gcd(x,seg[seg[node].lr].val%INF);
}
seg[node].val=(seg[node].val/INF)*INF+x;
}
long long sum0(int l,int r,int node,int nodel=0,int noder=c-1) {
if (r<nodel||l>noder) {
return 0;
}
if (l<=nodel&&noder<=r) {
//printf(" %lld\n",seg[node].val);
return seg[node].val%INF;
}
long long ret=0;
int mid=(nodel+noder)/2;
if (seg[node].val/INF==0) {
ret=gcd(sum0(l,r,node+1,nodel,mid),ret);
}
else if (seg[node].lr!=-1) {
ret=gcd(sum0(l,r,seg[node].lr,nodel,mid),ret);
}
if (seg[node].val/INF==1) {
ret=gcd(sum0(l,r,node+1,mid+1,noder),ret);
}
else if (seg[node].lr!=-1) {
ret=gcd(sum0(l,r,seg[node].lr,mid+1,noder),ret);
}
//printf("%lld\n",ret);
return ret;
}
const int I=1e6;
int arr[700000];
void init2() {
arr[s++]=3*I-1;
}
void update2(int x,int y,long long v,int node=0,int nodel=0,int noder=r-1) {
if (nodel==noder) {
if (root[node]==-1) {
init0(node);
}
update0(y,v,root[node]);
return;
}
int mid=(nodel+noder)/2;
if (x<=mid) {
if (arr[node]/I==0) {
update2(x,y,v,node+1,nodel,mid);
}
if (arr[node]/I==1) {
if (arr[node]%I==I-1) {
arr[node]=(arr[node]/I)*I+s;
arr[s++]=3*I-1;
}
update2(x,y,v,arr[node]%I,nodel,mid);
}
if (arr[node]/I==2) {
arr[node]-=2*I;
arr[s++]=3*I-1;
update2(x,y,v,node+1,nodel,mid);
}
}
else {
if (arr[node]/I==0) {
if (arr[node]%I==I-1) {
arr[node]=(arr[node]/I)*I+s;
arr[s++]=3*I-1;
}
update2(x,y,v,arr[node]%I,mid+1,noder);
}
if (arr[node]/I==1) {
update2(x,y,v,node+1,mid+1,noder);
}
if (arr[node]/I==2) {
arr[node]-=I;
arr[s++]=3*I-1;
update2(x,y,v,node+1,mid+1,noder);
}
}
long long val=0;
if (arr[node]/I==0) {
val=gcd(sum0(y,y,root[node+1]),val);
}
else if (arr[node]%I!=I-1) {
val=gcd(sum0(y,y,root[arr[node]%I]),val);
}
if (arr[node]/I==1) {
val=gcd(sum0(y,y,root[node+1]),val);
}
else if (arr[node]%I!=I-1) {
val=gcd(sum0(y,y,root[arr[node]%I]),val);
}
if (root[node]==-1) {
init0(node);
}
update0(y,val,root[node]);
}
long long sum2(int xl,int xr,int yl,int yr,int node=0,int nodel=0,int noder=r-1) {
if (xr<nodel||xl>noder) {
return 0;
}
if (xl<=nodel&&noder<=xr) {
return sum0(yl,yr,root[node]);
}
int mid=(nodel+noder)/2;
long long ret=0;
if (arr[node]/I==0) {
ret=gcd(ret,sum2(xl,xr,yl,yr,node+1,nodel,mid));
}
else if (arr[node]%I!=I-1) {
ret=gcd(ret,sum2(xl,xr,yl,yr,arr[node]%I,nodel,mid));
}
if (arr[node]/I==1) {
ret=gcd(ret,sum2(xl,xr,yl,yr,node+1,mid+1,noder));
}
else if (arr[node]%I!=I-1) {
ret=gcd(ret,sum2(xl,xr,yl,yr,arr[node]%I,mid+1,noder));
}
return ret;
}
void init(int x,int y) {
r=x;
c=y;
init2();
memset(root,-1,sizeof(root));
}
void update(int p,int q,long long k) {
update2(p,q,k);
}
long long calculate(int p,int q,int u,int v) {
return sum2(p,u,q,v);
}
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;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3072 KB |
Output is correct |
2 |
Correct |
6 ms |
3072 KB |
Output is correct |
3 |
Correct |
7 ms |
3072 KB |
Output is correct |
4 |
Correct |
6 ms |
3072 KB |
Output is correct |
5 |
Correct |
6 ms |
3072 KB |
Output is correct |
6 |
Correct |
6 ms |
3072 KB |
Output is correct |
7 |
Correct |
6 ms |
3072 KB |
Output is correct |
8 |
Correct |
6 ms |
3072 KB |
Output is correct |
9 |
Correct |
8 ms |
3072 KB |
Output is correct |
10 |
Correct |
6 ms |
3072 KB |
Output is correct |
11 |
Correct |
6 ms |
3072 KB |
Output is correct |
12 |
Correct |
6 ms |
3072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3072 KB |
Output is correct |
2 |
Correct |
6 ms |
3072 KB |
Output is correct |
3 |
Correct |
6 ms |
3072 KB |
Output is correct |
4 |
Correct |
674 ms |
12024 KB |
Output is correct |
5 |
Correct |
472 ms |
12152 KB |
Output is correct |
6 |
Correct |
560 ms |
8952 KB |
Output is correct |
7 |
Correct |
613 ms |
8952 KB |
Output is correct |
8 |
Correct |
433 ms |
7672 KB |
Output is correct |
9 |
Correct |
590 ms |
8896 KB |
Output is correct |
10 |
Correct |
550 ms |
8440 KB |
Output is correct |
11 |
Correct |
6 ms |
3072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3072 KB |
Output is correct |
2 |
Correct |
7 ms |
3072 KB |
Output is correct |
3 |
Correct |
7 ms |
3072 KB |
Output is correct |
4 |
Correct |
6 ms |
3072 KB |
Output is correct |
5 |
Correct |
6 ms |
3072 KB |
Output is correct |
6 |
Correct |
6 ms |
3072 KB |
Output is correct |
7 |
Correct |
6 ms |
3072 KB |
Output is correct |
8 |
Correct |
6 ms |
3072 KB |
Output is correct |
9 |
Correct |
6 ms |
3072 KB |
Output is correct |
10 |
Correct |
6 ms |
3072 KB |
Output is correct |
11 |
Correct |
6 ms |
3072 KB |
Output is correct |
12 |
Correct |
1087 ms |
13560 KB |
Output is correct |
13 |
Correct |
1704 ms |
6904 KB |
Output is correct |
14 |
Correct |
359 ms |
4216 KB |
Output is correct |
15 |
Correct |
2005 ms |
8440 KB |
Output is correct |
16 |
Correct |
261 ms |
12920 KB |
Output is correct |
17 |
Correct |
893 ms |
10032 KB |
Output is correct |
18 |
Correct |
1405 ms |
13432 KB |
Output is correct |
19 |
Correct |
1244 ms |
13432 KB |
Output is correct |
20 |
Correct |
1185 ms |
12772 KB |
Output is correct |
21 |
Correct |
6 ms |
3072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3072 KB |
Output is correct |
2 |
Correct |
6 ms |
3072 KB |
Output is correct |
3 |
Correct |
6 ms |
3072 KB |
Output is correct |
4 |
Correct |
6 ms |
3072 KB |
Output is correct |
5 |
Correct |
7 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
6 ms |
3072 KB |
Output is correct |
8 |
Correct |
6 ms |
3072 KB |
Output is correct |
9 |
Correct |
6 ms |
3064 KB |
Output is correct |
10 |
Correct |
6 ms |
3072 KB |
Output is correct |
11 |
Correct |
6 ms |
3072 KB |
Output is correct |
12 |
Correct |
678 ms |
11828 KB |
Output is correct |
13 |
Correct |
495 ms |
12152 KB |
Output is correct |
14 |
Correct |
556 ms |
9080 KB |
Output is correct |
15 |
Correct |
601 ms |
8952 KB |
Output is correct |
16 |
Correct |
420 ms |
7672 KB |
Output is correct |
17 |
Correct |
590 ms |
8824 KB |
Output is correct |
18 |
Correct |
541 ms |
8440 KB |
Output is correct |
19 |
Correct |
1084 ms |
13560 KB |
Output is correct |
20 |
Correct |
1720 ms |
7032 KB |
Output is correct |
21 |
Correct |
346 ms |
4216 KB |
Output is correct |
22 |
Correct |
1992 ms |
8580 KB |
Output is correct |
23 |
Correct |
266 ms |
12920 KB |
Output is correct |
24 |
Correct |
923 ms |
9996 KB |
Output is correct |
25 |
Correct |
1461 ms |
13304 KB |
Output is correct |
26 |
Correct |
1227 ms |
13432 KB |
Output is correct |
27 |
Correct |
1185 ms |
12920 KB |
Output is correct |
28 |
Correct |
773 ms |
127564 KB |
Output is correct |
29 |
Correct |
2008 ms |
142656 KB |
Output is correct |
30 |
Correct |
4074 ms |
104604 KB |
Output is correct |
31 |
Correct |
3802 ms |
80916 KB |
Output is correct |
32 |
Correct |
632 ms |
4472 KB |
Output is correct |
33 |
Correct |
830 ms |
5628 KB |
Output is correct |
34 |
Correct |
541 ms |
139768 KB |
Output is correct |
35 |
Correct |
1379 ms |
72952 KB |
Output is correct |
36 |
Correct |
2470 ms |
140284 KB |
Output is correct |
37 |
Correct |
2075 ms |
140284 KB |
Output is correct |
38 |
Correct |
2084 ms |
139908 KB |
Output is correct |
39 |
Correct |
1792 ms |
108536 KB |
Output is correct |
40 |
Correct |
6 ms |
3072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3072 KB |
Output is correct |
2 |
Correct |
7 ms |
3200 KB |
Output is correct |
3 |
Correct |
6 ms |
3072 KB |
Output is correct |
4 |
Correct |
6 ms |
3072 KB |
Output is correct |
5 |
Correct |
6 ms |
3072 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
6 ms |
3072 KB |
Output is correct |
8 |
Correct |
6 ms |
3072 KB |
Output is correct |
9 |
Correct |
8 ms |
3072 KB |
Output is correct |
10 |
Correct |
6 ms |
3072 KB |
Output is correct |
11 |
Correct |
6 ms |
3072 KB |
Output is correct |
12 |
Correct |
685 ms |
11936 KB |
Output is correct |
13 |
Correct |
495 ms |
12408 KB |
Output is correct |
14 |
Correct |
547 ms |
8952 KB |
Output is correct |
15 |
Correct |
599 ms |
8696 KB |
Output is correct |
16 |
Correct |
437 ms |
7668 KB |
Output is correct |
17 |
Correct |
604 ms |
8952 KB |
Output is correct |
18 |
Correct |
543 ms |
8444 KB |
Output is correct |
19 |
Correct |
1095 ms |
13508 KB |
Output is correct |
20 |
Correct |
1711 ms |
7288 KB |
Output is correct |
21 |
Correct |
344 ms |
4216 KB |
Output is correct |
22 |
Correct |
1984 ms |
8312 KB |
Output is correct |
23 |
Correct |
273 ms |
13048 KB |
Output is correct |
24 |
Correct |
901 ms |
9908 KB |
Output is correct |
25 |
Correct |
1417 ms |
13304 KB |
Output is correct |
26 |
Correct |
1269 ms |
13688 KB |
Output is correct |
27 |
Correct |
1164 ms |
13048 KB |
Output is correct |
28 |
Correct |
812 ms |
127728 KB |
Output is correct |
29 |
Correct |
2013 ms |
142712 KB |
Output is correct |
30 |
Correct |
4116 ms |
104612 KB |
Output is correct |
31 |
Correct |
3885 ms |
80684 KB |
Output is correct |
32 |
Correct |
635 ms |
4344 KB |
Output is correct |
33 |
Correct |
821 ms |
5756 KB |
Output is correct |
34 |
Correct |
539 ms |
139768 KB |
Output is correct |
35 |
Correct |
1391 ms |
73260 KB |
Output is correct |
36 |
Correct |
2508 ms |
140152 KB |
Output is correct |
37 |
Correct |
2115 ms |
140204 KB |
Output is correct |
38 |
Correct |
2058 ms |
139828 KB |
Output is correct |
39 |
Runtime error |
1139 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
40 |
Halted |
0 ms |
0 KB |
- |