oj.uz

Submission #218669

# Submission time Handle Problem Language Result Execution time Memory
218669 2020-04-02T13:37:30 Z urd05 Game (IOI13_game) C++14
80 / 100
 4402 ms 256008 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[16000000];
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 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 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 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 683 ms 11484 KB Output is correct
5 Correct 473 ms 11884 KB Output is correct
6 Correct 556 ms 8696 KB Output is correct
7 Correct 597 ms 8444 KB Output is correct
8 Correct 430 ms 7288 KB Output is correct
9 Correct 603 ms 8440 KB Output is correct
10 Correct 572 ms 8184 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 8 ms 3072 KB Output is correct
3 Correct 8 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 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 1132 ms 13376 KB Output is correct
13 Correct 1713 ms 6692 KB Output is correct
14 Correct 354 ms 4020 KB Output is correct
15 Correct 1997 ms 8236 KB Output is correct
16 Correct 265 ms 12664 KB Output is correct
17 Correct 886 ms 9592 KB Output is correct
18 Correct 1408 ms 13208 KB Output is correct
19 Correct 1228 ms 13176 KB Output is correct
20 Correct 1153 ms 12584 KB Output is correct
21 Correct 7 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 8 ms 3072 KB Output is correct
3 Correct 8 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 6 ms 3072 KB Output is correct
7 Correct 7 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 675 ms 11640 KB Output is correct
13 Correct 473 ms 11768 KB Output is correct
14 Correct 549 ms 8568 KB Output is correct
15 Correct 597 ms 8568 KB Output is correct
16 Correct 424 ms 7288 KB Output is correct
17 Correct 576 ms 8440 KB Output is correct
18 Correct 571 ms 8044 KB Output is correct
19 Correct 1134 ms 13176 KB Output is correct
20 Correct 1774 ms 6572 KB Output is correct
21 Correct 375 ms 4088 KB Output is correct
22 Correct 2001 ms 7904 KB Output is correct
23 Correct 268 ms 12668 KB Output is correct
24 Correct 900 ms 9464 KB Output is correct
25 Correct 1447 ms 13060 KB Output is correct
26 Correct 1249 ms 13168 KB Output is correct
27 Correct 1160 ms 12536 KB Output is correct
28 Correct 773 ms 127372 KB Output is correct
29 Correct 1984 ms 142456 KB Output is correct
30 Correct 4058 ms 104312 KB Output is correct
31 Correct 3801 ms 80508 KB Output is correct
32 Correct 666 ms 4088 KB Output is correct
33 Correct 850 ms 5360 KB Output is correct
34 Correct 578 ms 139764 KB Output is correct
35 Correct 1454 ms 73988 KB Output is correct
36 Correct 2575 ms 141272 KB Output is correct
37 Correct 2149 ms 141412 KB Output is correct
38 Correct 2048 ms 140920 KB Output is correct
39 Correct 1747 ms 109692 KB Output is correct
40 Correct 6 ms 3068 KB Output is correct

Subtask #5
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 7 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 693 ms 13048 KB Output is correct
13 Correct 469 ms 13304 KB Output is correct
14 Correct 565 ms 10104 KB Output is correct
15 Correct 600 ms 9932 KB Output is correct
16 Correct 429 ms 8696 KB Output is correct
17 Correct 580 ms 9968 KB Output is correct
18 Correct 543 ms 9596 KB Output is correct
19 Correct 1082 ms 14584 KB Output is correct
20 Correct 1704 ms 8176 KB Output is correct
21 Correct 355 ms 5368 KB Output is correct
22 Correct 2017 ms 9516 KB Output is correct
23 Correct 262 ms 14072 KB Output is correct
24 Correct 899 ms 11108 KB Output is correct
25 Correct 1431 ms 14456 KB Output is correct
26 Correct 1231 ms 14712 KB Output is correct
27 Correct 1153 ms 14072 KB Output is correct
28 Correct 786 ms 128632 KB Output is correct
29 Correct 2071 ms 143740 KB Output is correct
30 Correct 4402 ms 105436 KB Output is correct
31 Correct 3970 ms 81828 KB Output is correct
32 Correct 699 ms 5368 KB Output is correct
33 Correct 882 ms 6520 KB Output is correct
34 Correct 642 ms 140664 KB Output is correct
35 Correct 1497 ms 73868 KB Output is correct
36 Correct 2776 ms 140912 KB Output is correct
37 Correct 2272 ms 140984 KB Output is correct
38 Correct 2128 ms 140308 KB Output is correct
39 Runtime error 1142 ms 256008 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -