Submission #218668

#	Time	Username	Problem	Language	Result	Execution time	Memory
218668		urd05	Game (IOI13_game)	C++14	80 / 100	4133 ms	249720 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20