oj.uz

Submission #218668

# Submission time Handle Problem Language Result Execution time Memory
218668 2020-04-02T13:34:55 Z urd05 Game (IOI13_game) C++14
80 / 100
 4133 ms 249720 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[15000000];
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;
      ^~~

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 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 3200 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Correct 7 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 695 ms 11548 KB Output is correct
5 Correct 494 ms 11768 KB Output is correct
6 Correct 579 ms 8688 KB Output is correct
7 Correct 603 ms 8344 KB Output is correct
8 Correct 436 ms 7416 KB Output is correct
9 Correct 580 ms 8440 KB Output is correct
10 Correct 533 ms 8056 KB Output is correct
11 Correct 6 ms 3072 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 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 1084 ms 13132 KB Output is correct
13 Correct 1720 ms 6944 KB Output is correct
14 Correct 354 ms 3960 KB Output is correct
15 Correct 2021 ms 7928 KB Output is correct
16 Correct 261 ms 12664 KB Output is correct
17 Correct 894 ms 9688 KB Output is correct
18 Correct 1430 ms 13176 KB Output is correct
19 Correct 1263 ms 13304 KB Output is correct
20 Correct 1157 ms 12664 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 7 ms 3072 KB Output is correct
3 Correct 6 ms 3072 KB Output is correct
4 Correct 8 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 697 ms 11644 KB Output is correct
13 Correct 502 ms 11896 KB Output is correct
14 Correct 554 ms 8572 KB Output is correct
15 Correct 594 ms 8312 KB Output is correct
16 Correct 443 ms 7416 KB Output is correct
17 Correct 583 ms 8440 KB Output is correct
18 Correct 533 ms 8056 KB Output is correct
19 Correct 1086 ms 13304 KB Output is correct
20 Correct 1712 ms 6676 KB Output is correct
21 Correct 346 ms 3960 KB Output is correct
22 Correct 1980 ms 7928 KB Output is correct
23 Correct 267 ms 12664 KB Output is correct
24 Correct 906 ms 9592 KB Output is correct
25 Correct 1469 ms 13048 KB Output is correct
26 Correct 1249 ms 13204 KB Output is correct
27 Correct 1178 ms 12548 KB Output is correct
28 Correct 766 ms 127224 KB Output is correct
29 Correct 2003 ms 142556 KB Output is correct
30 Correct 4133 ms 104336 KB Output is correct
31 Correct 3808 ms 80388 KB Output is correct
32 Correct 643 ms 4088 KB Output is correct
33 Correct 830 ms 5372 KB Output is correct
34 Correct 544 ms 139512 KB Output is correct
35 Correct 1380 ms 72912 KB Output is correct
36 Correct 2524 ms 139868 KB Output is correct
37 Correct 2161 ms 140004 KB Output is correct
38 Correct 2118 ms 139356 KB Output is correct
39 Correct 1757 ms 108236 KB Output is correct
40 Correct 6 ms 3072 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 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 667 ms 11640 KB Output is correct
13 Correct 522 ms 11816 KB Output is correct
14 Correct 571 ms 8824 KB Output is correct
15 Correct 639 ms 8568 KB Output is correct
16 Correct 451 ms 7416 KB Output is correct
17 Correct 583 ms 8440 KB Output is correct
18 Correct 549 ms 8264 KB Output is correct
19 Correct 1110 ms 13176 KB Output is correct
20 Correct 1780 ms 6776 KB Output is correct
21 Correct 399 ms 3960 KB Output is correct
22 Correct 1972 ms 8104 KB Output is correct
23 Correct 270 ms 12664 KB Output is correct
24 Correct 885 ms 9592 KB Output is correct
25 Correct 1421 ms 12920 KB Output is correct
26 Correct 1255 ms 13180 KB Output is correct
27 Correct 1157 ms 12544 KB Output is correct
28 Correct 767 ms 127352 KB Output is correct
29 Correct 1982 ms 142252 KB Output is correct
30 Correct 4009 ms 104176 KB Output is correct
31 Correct 3815 ms 80436 KB Output is correct
32 Correct 636 ms 4216 KB Output is correct
33 Correct 817 ms 5368 KB Output is correct
34 Correct 561 ms 139640 KB Output is correct
35 Correct 1354 ms 72608 KB Output is correct
36 Correct 2496 ms 139940 KB Output is correct
37 Correct 2117 ms 139892 KB Output is correct
38 Correct 2052 ms 139344 KB Output is correct
39 Execution timed out 1043 ms 249720 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -