oj.uz

Submission #258228

# Submission time Handle Problem Language Result Execution time Memory
258228 2020-08-05T15:01:58 Z eohomegrownapps Game (IOI13_game) C++14
63 / 100
 1900 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 (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){
        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 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 384 KB Output is correct
6 Correct 2 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 360 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 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 586 ms 18424 KB Output is correct
5 Correct 409 ms 18168 KB Output is correct
6 Correct 639 ms 15224 KB Output is correct
7 Correct 715 ms 14968 KB Output is correct
8 Correct 430 ms 9976 KB Output is correct
9 Correct 735 ms 14972 KB Output is correct
10 Correct 602 ms 14616 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 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 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 931 ms 22780 KB Output is correct
13 Correct 1437 ms 9848 KB Output is correct
14 Correct 314 ms 2040 KB Output is correct
15 Correct 1705 ms 13688 KB Output is correct
16 Correct 271 ms 27896 KB Output is correct
17 Correct 1106 ms 17528 KB Output is correct
18 Correct 1900 ms 28244 KB Output is correct
19 Correct 1645 ms 28536 KB Output is correct
20 Correct 1505 ms 28132 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 1 ms 384 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 576 ms 18388 KB Output is correct
13 Correct 442 ms 18168 KB Output is correct
14 Correct 670 ms 15096 KB Output is correct
15 Correct 684 ms 14864 KB Output is correct
16 Correct 428 ms 9976 KB Output is correct
17 Correct 745 ms 15096 KB Output is correct
18 Correct 653 ms 14632 KB Output is correct
19 Correct 958 ms 22668 KB Output is correct
20 Correct 1376 ms 9720 KB Output is correct
21 Correct 305 ms 2040 KB Output is correct
22 Correct 1638 ms 13612 KB Output is correct
23 Correct 312 ms 27836 KB Output is correct
24 Correct 1121 ms 17528 KB Output is correct
25 Correct 1872 ms 28312 KB Output is correct
26 Correct 1594 ms 28476 KB Output is correct
27 Correct 1521 ms 27828 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 -

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 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 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 624 ms 18424 KB Output is correct
13 Correct 418 ms 18168 KB Output is correct
14 Correct 582 ms 15100 KB Output is correct
15 Correct 658 ms 14852 KB Output is correct
16 Correct 411 ms 10360 KB Output is correct
17 Correct 630 ms 15096 KB Output is correct
18 Correct 595 ms 14428 KB Output is correct
19 Correct 901 ms 22640 KB Output is correct
20 Correct 1383 ms 9924 KB Output is correct
21 Correct 353 ms 1912 KB Output is correct
22 Correct 1664 ms 13688 KB Output is correct
23 Correct 267 ms 27896 KB Output is correct
24 Correct 1086 ms 17656 KB Output is correct
25 Correct 1834 ms 28408 KB Output is correct
26 Correct 1666 ms 28296 KB Output is correct
27 Correct 1558 ms 27512 KB Output is correct
28 Runtime error 709 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -