oj.uz

Submission #258223

# Submission time Handle Problem Language Result Execution time Memory
258223 2020-08-05T14:58:43 Z eohomegrownapps Game (IOI13_game) C++14
63 / 100
 1720 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;
    ll v;
    NodeY *l = NULL;
    NodeY *r = NULL;
    NodeY(int _s, int _e){
        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 (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){
        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) {
    /* ... */
    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 372 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 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 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 609 ms 17296 KB Output is correct
5 Correct 410 ms 17392 KB Output is correct
6 Correct 545 ms 14452 KB Output is correct
7 Correct 687 ms 14056 KB Output is correct
8 Correct 428 ms 9336 KB Output is correct
9 Correct 576 ms 14200 KB Output is correct
10 Correct 549 ms 13784 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.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 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 901 ms 21924 KB Output is correct
13 Correct 1412 ms 9096 KB Output is correct
14 Correct 348 ms 1568 KB Output is correct
15 Correct 1625 ms 12920 KB Output is correct
16 Correct 253 ms 27384 KB Output is correct
17 Correct 963 ms 16872 KB Output is correct
18 Correct 1720 ms 27592 KB Output is correct
19 Correct 1607 ms 27828 KB Output is correct
20 Correct 1477 ms 27108 KB Output is correct
21 Correct 1 ms 372 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 2 ms 512 KB Output is correct
3 Correct 1 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 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 569 ms 17272 KB Output is correct
13 Correct 393 ms 17272 KB Output is correct
14 Correct 554 ms 14328 KB Output is correct
15 Correct 658 ms 14200 KB Output is correct
16 Correct 405 ms 9208 KB Output is correct
17 Correct 604 ms 14328 KB Output is correct
18 Correct 564 ms 13816 KB Output is correct
19 Correct 911 ms 21880 KB Output is correct
20 Correct 1381 ms 9208 KB Output is correct
21 Correct 304 ms 1332 KB Output is correct
22 Correct 1665 ms 12920 KB Output is correct
23 Correct 259 ms 27128 KB Output is correct
24 Correct 946 ms 16632 KB Output is correct
25 Correct 1651 ms 27768 KB Output is correct
26 Correct 1358 ms 27512 KB Output is correct
27 Correct 1372 ms 27000 KB Output is correct
28 Runtime error 680 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 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 0 ms 256 KB Output is correct
8 Correct 0 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 562 ms 17272 KB Output is correct
13 Correct 393 ms 17400 KB Output is correct
14 Correct 547 ms 14464 KB Output is correct
15 Correct 599 ms 14200 KB Output is correct
16 Correct 394 ms 9208 KB Output is correct
17 Correct 607 ms 14328 KB Output is correct
18 Correct 571 ms 13944 KB Output is correct
19 Correct 898 ms 21944 KB Output is correct
20 Correct 1382 ms 9040 KB Output is correct
21 Correct 310 ms 1272 KB Output is correct
22 Correct 1623 ms 12852 KB Output is correct
23 Correct 252 ms 27128 KB Output is correct
24 Correct 926 ms 16888 KB Output is correct
25 Correct 1684 ms 27460 KB Output is correct
26 Correct 1447 ms 27456 KB Output is correct
27 Correct 1388 ms 26872 KB Output is correct
28 Runtime error 702 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -