Submission #258213

#	Time	Username	Problem	Language	Result	Execution time	Memory
258213		eohomegrownapps	Game (IOI13_game)	C++14	36 / 100	13091 ms	82700 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long 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;

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

    void makeL(){
        if (l!=NULL){
            return;
        }
        l = new NodeY(s,m);
    }

    void makeR(){
        if (r!=NULL){
            return;
        }
        r = new NodeY(m+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<=m){
            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;
        }
        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){
        //cout<<s<<' '<<e<<' '<<"com\n";
        v = 0;
        if (lc==NULL&&rc==NULL){
            return;
        }
        if (lc!=NULL){
            v = gcd2(v,lc->v);
        }
        if (rc!=NULL){
            v = gcd2(v,rc->v);
        }
        if (s==e){return;}
        makeL();
        makeR();
        l->combine((lc==NULL)?(NodeY*)NULL:lc->l, (rc==NULL)?(NodeY*)NULL:rc->l);
        r->combine((lc==NULL)?(NodeY*)NULL:lc->r, (rc==NULL)?(NodeY*)NULL:rc->r);
    }
};

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

    void makeL(){
        if (l!=NULL){
            return;
        }
        l = new NodeX(s,m);
    }

    void makeR(){
        if (r!=NULL){
            return;
        }
        r = new NodeX(m+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;
        }
        makeL();makeR();
        if (indx<=m){
            l->update(indx,indy,val);
        } else {
            r->update(indx,indy,val);
        }
        //cout<<"combine\n";
        v->combine(l->v,r->v); //???
    }

    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){
        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) {
    /* ... */
    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: 0 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20