oj.uz

Submission #218666

# Submission time Handle Problem Language Result Execution time Memory
218666 2020-04-02T13:30:03 Z urd05 Game (IOI13_game) C++14
80 / 100
 4149 ms 256004 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[19000000];
int s=0;
int sz=0;
const long long INF=2e18;
int root[680000];
    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[680000];
 
    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 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 2944 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 6 ms 2944 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 2944 KB Output is correct
12 Correct 6 ms 2944 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 695 ms 12152 KB Output is correct
5 Correct 507 ms 12536 KB Output is correct
6 Correct 554 ms 9336 KB Output is correct
7 Correct 616 ms 9248 KB Output is correct
8 Correct 439 ms 8312 KB Output is correct
9 Correct 579 ms 9208 KB Output is correct
10 Correct 544 ms 8824 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 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 2944 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 7 ms 2944 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 6 ms 2944 KB Output is correct
11 Correct 7 ms 2944 KB Output is correct
12 Correct 1104 ms 13996 KB Output is correct
13 Correct 1731 ms 7420 KB Output is correct
14 Correct 345 ms 4728 KB Output is correct
15 Correct 1980 ms 8676 KB Output is correct
16 Correct 272 ms 13304 KB Output is correct
17 Correct 890 ms 10232 KB Output is correct
18 Correct 1421 ms 13816 KB Output is correct
19 Correct 1255 ms 14072 KB Output is correct
20 Correct 1156 ms 13176 KB Output is correct
21 Correct 6 ms 2944 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 7 ms 3072 KB Output is correct
3 Correct 6 ms 3072 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Correct 7 ms 2944 KB Output is correct
12 Correct 692 ms 12332 KB Output is correct
13 Correct 493 ms 12664 KB Output is correct
14 Correct 572 ms 9464 KB Output is correct
15 Correct 584 ms 9080 KB Output is correct
16 Correct 428 ms 8056 KB Output is correct
17 Correct 601 ms 9336 KB Output is correct
18 Correct 555 ms 8824 KB Output is correct
19 Correct 1117 ms 13912 KB Output is correct
20 Correct 1717 ms 7544 KB Output is correct
21 Correct 353 ms 4600 KB Output is correct
22 Correct 1980 ms 8824 KB Output is correct
23 Correct 270 ms 13432 KB Output is correct
24 Correct 899 ms 10436 KB Output is correct
25 Correct 1465 ms 13816 KB Output is correct
26 Correct 1300 ms 13800 KB Output is correct
27 Correct 1184 ms 13304 KB Output is correct
28 Correct 779 ms 127992 KB Output is correct
29 Correct 1990 ms 142968 KB Output is correct
30 Correct 4149 ms 104824 KB Output is correct
31 Correct 3885 ms 81016 KB Output is correct
32 Correct 645 ms 4728 KB Output is correct
33 Correct 818 ms 6008 KB Output is correct
34 Correct 546 ms 140108 KB Output is correct
35 Correct 1430 ms 73336 KB Output is correct
36 Correct 2504 ms 140508 KB Output is correct
37 Correct 2122 ms 140524 KB Output is correct
38 Correct 2117 ms 140152 KB Output is correct
39 Correct 1807 ms 108920 KB Output is correct
40 Correct 6 ms 2944 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 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 2944 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 6 ms 2944 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 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Correct 707 ms 12280 KB Output is correct
13 Correct 491 ms 12536 KB Output is correct
14 Correct 557 ms 9336 KB Output is correct
15 Correct 604 ms 9176 KB Output is correct
16 Correct 445 ms 8056 KB Output is correct
17 Correct 608 ms 9188 KB Output is correct
18 Correct 554 ms 8824 KB Output is correct
19 Correct 1119 ms 13816 KB Output is correct
20 Correct 1756 ms 7416 KB Output is correct
21 Correct 367 ms 4600 KB Output is correct
22 Correct 1982 ms 8712 KB Output is correct
23 Correct 269 ms 13432 KB Output is correct
24 Correct 903 ms 10360 KB Output is correct
25 Correct 1458 ms 13592 KB Output is correct
26 Correct 1267 ms 13816 KB Output is correct
27 Correct 1163 ms 13304 KB Output is correct
28 Correct 793 ms 127868 KB Output is correct
29 Correct 2019 ms 142968 KB Output is correct
30 Correct 4146 ms 104440 KB Output is correct
31 Correct 3804 ms 81020 KB Output is correct
32 Correct 670 ms 4600 KB Output is correct
33 Correct 844 ms 5880 KB Output is correct
34 Correct 547 ms 139896 KB Output is correct
35 Correct 1396 ms 73208 KB Output is correct
36 Correct 2534 ms 140244 KB Output is correct
37 Correct 2160 ms 140244 KB Output is correct
38 Correct 2115 ms 139468 KB Output is correct
39 Runtime error 1158 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -