oj.uz

Submission #218909

# Submission time Handle Problem Language Result Execution time Memory
218909 2020-04-03T05:44:38 Z urd05 Game (IOI13_game) C++14
100 / 100
 5747 ms 231484 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];
int lr[19500000];
int s=0;
int sz=0;
const long long INF=2e18;

int root[700000];
int arr[700000];
    void init0(int node) {
        root[node]=sz;
        value[sz]=2*INF;
        lr[sz]=-1;
        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]==-1) {
                    lr[node]=sz;
                    value[sz]=2*INF;
                    lr[sz]=-1;
                    sz++;
                }
                update0(y,v,lr[node],nodel,mid);
            }
            if (value[node]/INF==2) {
                value[node]-=2*INF;
                value[sz]=2*INF;
                lr[sz]=-1;
                sz++;
                update0(y,v,node+1,nodel,mid);
            }
        }
        else {
            if (value[node]/INF==0) {
                if (lr[node]==-1) {
                    lr[node]=sz;
                    value[sz]=2*INF;
                    lr[sz]=-1;
                    sz++;
                }
                update0(y,v,lr[node],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;
                lr[sz]=-1;
                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]!=-1) {
            x=gcd(x,value[lr[node]]%INF);
        }
        if (value[node]/INF==1) {
            x=gcd(x,value[node+1]%INF);
        }
        else if (lr[node]!=-1) {
            x=gcd(x,value[lr[node]]%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]!=-1) {
            ret=gcd(sum0(l,r,lr[node],nodel,mid),ret);
        }
        if (value[node]/INF==1) {
            ret=gcd(sum0(l,r,node+1,mid+1,noder),ret);
        }
        else if (lr[node]!=-1) {
            ret=gcd(sum0(l,r,lr[node],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;
    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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3048 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 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 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 6 ms 3072 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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 681 ms 14588 KB Output is correct
5 Correct 470 ms 14584 KB Output is correct
6 Correct 560 ms 12024 KB Output is correct
7 Correct 609 ms 11788 KB Output is correct
8 Correct 421 ms 10744 KB Output is correct
9 Correct 600 ms 11896 KB Output is correct
10 Correct 544 ms 11512 KB Output is correct
11 Correct 6 ms 3200 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3200 KB Output is correct
3 Correct 6 ms 3200 KB Output is correct
4 Correct 6 ms 3072 KB Output is correct
5 Correct 6 ms 3072 KB Output is correct
6 Correct 7 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 7 ms 3200 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Correct 6 ms 3072 KB Output is correct
12 Correct 1107 ms 15808 KB Output is correct
13 Correct 1699 ms 9976 KB Output is correct
14 Correct 352 ms 8316 KB Output is correct
15 Correct 1962 ms 11264 KB Output is correct
16 Correct 254 ms 14456 KB Output is correct
17 Correct 896 ms 13052 KB Output is correct
18 Correct 1385 ms 15992 KB Output is correct
19 Correct 1223 ms 16052 KB Output is correct
20 Correct 1130 ms 15480 KB Output is correct
21 Correct 6 ms 3072 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory 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 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 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 721 ms 14772 KB Output is correct
13 Correct 492 ms 14712 KB Output is correct
14 Correct 555 ms 12120 KB Output is correct
15 Correct 590 ms 11760 KB Output is correct
16 Correct 426 ms 10744 KB Output is correct
17 Correct 584 ms 11808 KB Output is correct
18 Correct 532 ms 11516 KB Output is correct
19 Correct 1100 ms 15596 KB Output is correct
20 Correct 1720 ms 9848 KB Output is correct
21 Correct 341 ms 8312 KB Output is correct
22 Correct 2011 ms 11200 KB Output is correct
23 Correct 261 ms 14456 KB Output is correct
24 Correct 897 ms 12920 KB Output is correct
25 Correct 1378 ms 15984 KB Output is correct
26 Correct 1219 ms 16168 KB Output is correct
27 Correct 1128 ms 15480 KB Output is correct
28 Correct 769 ms 101888 KB Output is correct
29 Correct 2094 ms 114204 KB Output is correct
30 Correct 4273 ms 85196 KB Output is correct
31 Correct 4003 ms 67116 KB Output is correct
32 Correct 629 ms 9672 KB Output is correct
33 Correct 799 ms 10744 KB Output is correct
34 Correct 558 ms 111480 KB Output is correct
35 Correct 1437 ms 61360 KB Output is correct
36 Correct 2619 ms 111804 KB Output is correct
37 Correct 2177 ms 111868 KB Output is correct
38 Correct 2113 ms 111352 KB Output is correct
39 Correct 1837 ms 88112 KB Output is correct
40 Correct 6 ms 3072 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 7 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 6 ms 3072 KB Output is correct
6 Correct 7 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 669 ms 14712 KB Output is correct
13 Correct 495 ms 14456 KB Output is correct
14 Correct 543 ms 12024 KB Output is correct
15 Correct 589 ms 11744 KB Output is correct
16 Correct 426 ms 10744 KB Output is correct
17 Correct 583 ms 11896 KB Output is correct
18 Correct 537 ms 11512 KB Output is correct
19 Correct 1121 ms 15664 KB Output is correct
20 Correct 1700 ms 9848 KB Output is correct
21 Correct 344 ms 8440 KB Output is correct
22 Correct 1955 ms 11316 KB Output is correct
23 Correct 266 ms 14712 KB Output is correct
24 Correct 880 ms 13232 KB Output is correct
25 Correct 1376 ms 16248 KB Output is correct
26 Correct 1243 ms 16188 KB Output is correct
27 Correct 1139 ms 15584 KB Output is correct
28 Correct 777 ms 101752 KB Output is correct
29 Correct 2091 ms 114124 KB Output is correct
30 Correct 4231 ms 84696 KB Output is correct
31 Correct 3775 ms 66936 KB Output is correct
32 Correct 623 ms 9592 KB Output is correct
33 Correct 803 ms 10488 KB Output is correct
34 Correct 549 ms 111352 KB Output is correct
35 Correct 1428 ms 61304 KB Output is correct
36 Correct 2588 ms 111916 KB Output is correct
37 Correct 2130 ms 111736 KB Output is correct
38 Correct 2132 ms 111364 KB Output is correct
39 Correct 1127 ms 204824 KB Output is correct
40 Correct 3305 ms 231484 KB Output is correct
41 Correct 5747 ms 166684 KB Output is correct
42 Correct 5176 ms 129296 KB Output is correct
43 Correct 1032 ms 229696 KB Output is correct
44 Correct 866 ms 10008 KB Output is correct
45 Correct 1815 ms 88488 KB Output is correct
46 Correct 3477 ms 229704 KB Output is correct
47 Correct 3473 ms 229636 KB Output is correct
48 Correct 3369 ms 229120 KB Output is correct
49 Correct 6 ms 3072 KB Output is correct