| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 218913 |
2020-04-03T06:18:15 Z |
urd05 |
게임 (IOI13_game) |
C++14 |
|
35 ms |
64128 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);
}
long long value[19500000];
__int128 lr[3900000];
__int128 divi=20040513;
__int128 base=divi*divi*divi*divi*divi-1;
int s=0;
int sz=0;
const long long INF=2e18;
__int128 cal[6];
void fillcal() {
cal[0]=1;
for(int i=1;i<6;i++) {
cal[i]=cal[i-1]*divi;
}
}
inline void change(int node,int val) {
int now=node/5;
lr[now]=(lr[now]/cal[node%5+1])*cal[node%5+1]+lr[now]%cal[node%5];
lr[now]+=val*cal[node%5];
}
int root[700000];
int arr[700000];
void init0(int node) {
root[node]=sz;
value[sz]=2*INF;
sz++;
}
void update0(int y,long long v,int node,int nodel=0,int noder=c-1) {
if (nodel==noder) {
value[node]=(value[node]/INF)*INF+v;
return;
}
int mid=(nodel+noder)/2;
if (y<=mid) {
if (value[node]/INF==0) {
update0(y,v,node+1,nodel,mid);
}
if (value[node]/INF==1) {
if ((lr[node/5]/cal[node%5])%divi==divi-1) {
change(node,sz);
value[sz]=2*INF;
sz++;
}
update0(y,v,(lr[node/5]/cal[node%5])%divi,nodel,mid);
}
if (value[node]/INF==2) {
value[node]-=2*INF;
value[sz]=2*INF;
sz++;
update0(y,v,node+1,nodel,mid);
}
}
else {
if (value[node]/INF==0) {
if ((lr[node/5]/cal[node%5])%divi==divi-1) {
change(node,sz);
sz++;
}
update0(y,v,(lr[node/5]/cal[node%5])%divi,mid+1,noder);
}
if (value[node]/INF==1) {
update0(y,v,node+1,mid+1,noder);
}
if (value[node]/INF==2) {
value[node]-=INF;
value[sz]=2*INF;
sz++;
update0(y,v,node+1,mid+1,noder);
}
}
long long x=0;
if (value[node]/INF==0) {
x=gcd(x,value[node+1]%INF);
}
else if ((lr[node/5]/cal[node%5])%divi!=divi-1) {
x=gcd(x,value[(lr[node/5]/cal[node%5])%divi]%INF);
}
if (value[node]/INF==1) {
x=gcd(x,value[node+1]%INF);
}
else if (((lr[node/5])/cal[node%5])%divi!=divi-1) {
x=gcd(x,value[((lr[node/5])/cal[node%5])%divi]%INF);
}
value[node]=(value[node]/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) {
return value[node]%INF;
}
long long ret=0;
int mid=(nodel+noder)/2;
if (value[node]/INF==0) {
ret=gcd(sum0(l,r,node+1,nodel,mid),ret);
}
else if (((lr[node/5])/cal[node%5])%divi!=divi-1) {
ret=gcd(sum0(l,r,((lr[node/5])/cal[node%5])%divi,nodel,mid),ret);
}
if (value[node]/INF==1) {
ret=gcd(sum0(l,r,node+1,mid+1,noder),ret);
}
else if (((lr[node/5])/cal[node%5])%divi!=divi-1) {
ret=gcd(sum0(l,r,((lr[node/5])/cal[node%5])%divi,mid+1,noder),ret);
}
return ret;
}
const int I=1e6;
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;
fillcal();
init2();
for(int i=0;i<3900000;i++) {
lr[i]=base;
}
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 |
Incorrect |
35 ms |
64128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
64128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
64120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
64120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
64120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
