oj.uz

Submission #258217

# Submission time Handle Problem Language Result Execution time Memory
258217 2020-08-05T14:52:17 Z eohomegrownapps Game (IOI13_game) C++14
63 / 100
 1751 ms 256004 KB 
#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, int ind){
        //cout<<s<<' '<<e<<' '<<"com\n";
        if (s==e){
            v=gcd2((lc==NULL)?0:lc->v,(rc==NULL)?0:rc->v);
            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,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,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){
        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

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 0 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 566 ms 19004 KB Output is correct
5 Correct 404 ms 21368 KB Output is correct
6 Correct 541 ms 18808 KB Output is correct
7 Correct 657 ms 18680 KB Output is correct
8 Correct 408 ms 13304 KB Output is correct
9 Correct 602 ms 18680 KB Output is correct
10 Correct 595 ms 18296 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 961 ms 21676 KB Output is correct
13 Correct 1484 ms 8880 KB Output is correct
14 Correct 324 ms 1244 KB Output is correct
15 Correct 1751 ms 12852 KB Output is correct
16 Correct 259 ms 27000 KB Output is correct
17 Correct 924 ms 16748 KB Output is correct
18 Correct 1671 ms 27400 KB Output is correct
19 Correct 1340 ms 27512 KB Output is correct
20 Correct 1386 ms 26920 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 564 ms 19236 KB Output is correct
13 Correct 401 ms 21088 KB Output is correct
14 Correct 529 ms 18852 KB Output is correct
15 Correct 591 ms 18552 KB Output is correct
16 Correct 395 ms 13432 KB Output is correct
17 Correct 734 ms 18680 KB Output is correct
18 Correct 564 ms 18296 KB Output is correct
19 Correct 885 ms 25800 KB Output is correct
20 Correct 1372 ms 13012 KB Output is correct
21 Correct 359 ms 5816 KB Output is correct
22 Correct 1673 ms 17276 KB Output is correct
23 Correct 271 ms 31260 KB Output is correct
24 Correct 985 ms 21368 KB Output is correct
25 Correct 1618 ms 32824 KB Output is correct
26 Correct 1305 ms 32760 KB Output is correct
27 Correct 1332 ms 32228 KB Output is correct
28 Runtime error 665 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 551 ms 19320 KB Output is correct
13 Correct 404 ms 21112 KB Output is correct
14 Correct 580 ms 18936 KB Output is correct
15 Correct 630 ms 18552 KB Output is correct
16 Correct 387 ms 13304 KB Output is correct
17 Correct 630 ms 18840 KB Output is correct
18 Correct 553 ms 18296 KB Output is correct
19 Correct 866 ms 25848 KB Output is correct
20 Correct 1332 ms 12736 KB Output is correct
21 Correct 332 ms 5880 KB Output is correct
22 Correct 1636 ms 17256 KB Output is correct
23 Correct 252 ms 31096 KB Output is correct
24 Correct 912 ms 21496 KB Output is correct
25 Correct 1620 ms 32584 KB Output is correct
26 Correct 1348 ms 32784 KB Output is correct
27 Correct 1484 ms 32108 KB Output is correct
28 Runtime error 669 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -