oj.uz

Submission #258213

# Submission time Handle Problem Language Result Execution time Memory
258213 2020-08-05T14:42:53 Z eohomegrownapps Game (IOI13_game) C++14
36 / 100
 13000 ms 82700 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){
        //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

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

Subtask #2
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 384 KB Output is correct
4 Execution timed out 13008 ms 23180 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 3585 ms 44156 KB Output is correct
13 Correct 3889 ms 20692 KB Output is correct
14 Correct 1799 ms 7920 KB Output is correct
15 Correct 6478 ms 36404 KB Output is correct
16 Correct 8026 ms 81284 KB Output is correct
17 Correct 4637 ms 60320 KB Output is correct
18 Correct 9737 ms 82308 KB Output is correct
19 Correct 9665 ms 82700 KB Output is correct
20 Correct 10227 ms 82012 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 256 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Execution timed out 13091 ms 22208 KB Time limit exceeded
13 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 4 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Execution timed out 13037 ms 23412 KB Time limit exceeded
13 Halted 0 ms 0 KB -