Submission #258294

#	Time	Username	Problem	Language	Result	Execution time	Memory
258294		eohomegrownapps	Game (IOI13_game)	C++14	63 / 100	1630 ms	256004 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long ll;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int n;

int nc=0;

struct NodeY{
    int s,e;
    ll v;
    NodeY *l = NULL;
    NodeY *r = NULL;
    NodeY(int _s, int _e){
        nc++;
        s=_s;e=_e;
        v=0;
    }

    void makeL(){
        if (l!=NULL){
            return;
        }
        l = new NodeY(s,(s+e)/2);
    }

    void makeR(){
        if (r!=NULL){
            return;
        }
        r = new NodeY((s+e)/2+1,e);
    }

    ll getL(){
        if (l==NULL){
            return 0;
        }
        return l->v; 
    }

    ll getR(){
        if (r==NULL){
            return 0;
        }
        return r->v;
    }

    void update(int ind, ll val){
        //cout<<"y "<<s<<' '<<e<<'\n';
        //cout<<"u "<<ind<<' '<<val<<'\n';
        if (s==e){
            v=val;
            return;
        }
        if (ind<=(s+e)/2){
            makeL();
            l->update(ind,val);
        } else {
            makeR();
            r->update(ind,val);
        }
        v=gcd2(getL(),getR());
    }

    ll queryL(int ya, int yb){
        if (l==NULL){
            return 0;
        }
        return l->query(ya,yb);
    }

    ll queryR(int ya, int yb){
        if (r==NULL){
            return 0;
        }
        return r->query(ya,yb);
    }

    ll query(int ya, int yb){
        if (s==ya&&e==yb){
            return v;
        }
        int m = (s+e)/2;
        if (yb<=m){
            return queryL(ya,yb);
        } else if (m<ya){
            return queryR(ya,yb);
        } else {
            return gcd2(queryL(ya,m),queryR(m+1,yb));
        }
    }

    void combine(NodeY *lc, NodeY *rc, int ind){
        //cout<<s<<' '<<e<<' '<<"com\n";
        int m = (s+e)/2;
        if (s==e){
            v=gcd2((lc==NULL)?0:lc->v,(rc==NULL)?0:rc->v);
            return;
        }
        if (lc==NULL&&rc==NULL){
            v=0;
            return;
        }
        if (ind<=m){
            makeL();
            l->combine((lc==NULL)?(NodeY*)NULL:lc->l,(rc==NULL)?(NodeY*)NULL:rc->l,ind);
        } else {
            makeR();
            r->combine((lc==NULL)?(NodeY*)NULL:lc->r,(rc==NULL)?(NodeY*)NULL:rc->r,ind);
        }
        v=gcd2((l==NULL)?0:l->v,(r==NULL)?0:r->v);
    }
};

struct NodeX{
    int s,e;
    NodeY *v;
    NodeX *l = NULL;
    NodeX *r = NULL;
    NodeX(int _s, int _e){
        nc++;
        s=_s;e=_e;
        v=new NodeY(0,n-1);
    }

    void makeL(){
        if (l!=NULL){
            return;
        }
        l = new NodeX(s,(s+e)/2);
    }

    void makeR(){
        if (r!=NULL){
            return;
        }
        r = new NodeX((s+e)/2+1,e);
    }

    void update(int indx, int indy, ll val){
        //cout<<"x "<<s<<' '<<e<<'\n';
        //cout<<"u "<<indx<<' '<<indy<<' '<<val<<'\n';
        if (s==e){
            v->update(indy,val);
            return;
        }
        if (indx<=(s+e)/2){
            makeL();
            l->update(indx,indy,val);
        } else {
            makeR();
            r->update(indx,indy,val);
        }
        //cout<<"combine\n";
        v->combine((l==NULL)?(NodeY*)NULL:l->v,(r==NULL)?(NodeY*)NULL:r->v,indy); //???
    }

    ll queryL(int xa, int xb, int ya, int yb){
        if (l==NULL){
            return 0;
        }
        return l->query(xa,xb,ya,yb);
    }

    ll queryR(int xa, int xb, int ya, int yb){
        if (r==NULL){
            return 0;
        }
        return r->query(xa,xb,ya,yb);
    }

    ll query(int xa, int xb, int ya, int yb){
        int m = (s+e)/2;
        assert(xa<=xb&&ya<=yb);
        if (s==xa&&e==xb){
            return v->query(ya,yb);
        }
        if (xb<=m){
            return queryL(xa,xb,ya,yb);
        } else if (m<xa){
            return queryR(xa,xb,ya,yb);
        } else {
            return gcd2(queryL(xa,m,ya,yb),queryR(m+1,xb,ya,yb));
        }
    }
};

NodeX *root;
int x,y;
void init(int R, int C) {
    /* ... */
    x=R;y=C;
    n=y;
    root = new NodeX(0,x-1);
}

void update(int P, int Q, long long K) {
    /* ... */
    root->update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    //cout<<nc<<'\n';
    return root->query(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: 0 / 17
• Subtask 5: 0 / 20