oj.uz

Submission #258296

# Submission time Handle Problem Language Result Execution time Memory
258296 2020-08-05T16:37:03 Z eohomegrownapps Game (IOI13_game) C++14
63 / 100
 1790 ms 97404 KB 
#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';
    assert(nc<=1000000);
    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 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 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 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 0 ms 256 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 0 ms 256 KB Output is correct
4 Correct 551 ms 21240 KB Output is correct
5 Correct 385 ms 21100 KB Output is correct
6 Correct 531 ms 18828 KB Output is correct
7 Correct 589 ms 18680 KB Output is correct
8 Correct 383 ms 13304 KB Output is correct
9 Correct 569 ms 18672 KB Output is correct
10 Correct 543 ms 18168 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 0 ms 384 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 896 ms 25496 KB Output is correct
13 Correct 1353 ms 12664 KB Output is correct
14 Correct 318 ms 4816 KB Output is correct
15 Correct 1614 ms 16672 KB Output is correct
16 Correct 246 ms 30712 KB Output is correct
17 Correct 904 ms 20344 KB Output is correct
18 Correct 1553 ms 31136 KB Output is correct
19 Correct 1342 ms 31100 KB Output is correct
20 Correct 1314 ms 30536 KB Output is correct
21 Correct 1 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 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 542 ms 21344 KB Output is correct
13 Correct 402 ms 21092 KB Output is correct
14 Correct 530 ms 18936 KB Output is correct
15 Correct 587 ms 18492 KB Output is correct
16 Correct 386 ms 13344 KB Output is correct
17 Correct 553 ms 18680 KB Output is correct
18 Correct 521 ms 18552 KB Output is correct
19 Correct 860 ms 25848 KB Output is correct
20 Correct 1372 ms 12664 KB Output is correct
21 Correct 342 ms 5684 KB Output is correct
22 Correct 1790 ms 17168 KB Output is correct
23 Correct 264 ms 31096 KB Output is correct
24 Correct 1036 ms 21460 KB Output is correct
25 Correct 1581 ms 32596 KB Output is correct
26 Correct 1363 ms 32828 KB Output is correct
27 Correct 1286 ms 32376 KB Output is correct
28 Runtime error 177 ms 97404 KB Execution killed with signal 11 (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 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 512 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 544 ms 21244 KB Output is correct
13 Correct 384 ms 21112 KB Output is correct
14 Correct 523 ms 18936 KB Output is correct
15 Correct 617 ms 18640 KB Output is correct
16 Correct 377 ms 13272 KB Output is correct
17 Correct 586 ms 18808 KB Output is correct
18 Correct 535 ms 18188 KB Output is correct
19 Correct 860 ms 25660 KB Output is correct
20 Correct 1383 ms 12772 KB Output is correct
21 Correct 315 ms 5728 KB Output is correct
22 Correct 1584 ms 17000 KB Output is correct
23 Correct 255 ms 31248 KB Output is correct
24 Correct 892 ms 21368 KB Output is correct
25 Correct 1529 ms 32836 KB Output is correct
26 Correct 1304 ms 33016 KB Output is correct
27 Correct 1231 ms 32376 KB Output is correct
28 Runtime error 147 ms 97400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -