oj.uz

Submission #65446

# Submission time Handle Problem Language Result Execution time Memory
65446 2018-08-07T15:52:33 Z edisonhello Game (IOI13_game) C++14
63 / 100
 3953 ms 257024 KB 
#include "game.h"
#include<bits/stdc++.h>

#define ll int_fast64_t

using namespace std;

ll gcd(ll a,ll b){
    while(b){
        a%=b; swap(a,b);
    } return a;
}

struct treap{
    treap *l,*r;
    ll v,g;
    int pri,key;
    void pull(){ g=gcd(gcd(l?l->g:0,r?r->g:0),v); }
    treap(int x,ll v):l(0),r(0),v(v),g(v),pri(rand()),key(x){}
};
treap *merge(treap *a,treap *b){
    if(!a)return b; if(!b)return a;
    if(a->pri>b->pri){
        a->r=merge(a->r,b);
        a->pull();
        return a;
    }
    else{
        b->l=merge(a,b->l);
        b->pull();
        return b;
    }
}
void split(treap *now,int key,treap *&a,treap *&b){
    if(!now){ a=b=0; return; }
    if(now->key<=key){
        a=now;
        split(now->r,key,a->r,b);
        a->pull();
    }
    else{
        b=now;
        split(now->l,key,a,b->l);
        b->pull();
    }
}

struct nodey{
    nodey *l,*r;
    treap *root;
    ll g;
    void pull(){ g=gcd(l?l->g:0,r?r->g:0); return; }
    nodey():l(0),r(0),root(0),g(0){}
};

struct nodex{
    nodex *l,*r;
    nodey *root;
    nodex():l(0),r(0),root(0){}
} *root;

int x,y;

void init(int R, int C){
    x=R; y=C;
}

#define mid ((l+r)>>1)
void modify(nodey *&now,int l,int r,int xtag,int my,ll v){
    if(!now)now=new nodey();
    if(l==r){
        treap *a,*b,*c,*d;
        split(now->root,xtag-1,a,d);
        split(d,xtag,b,c);
        if(b)b->v=b->g=v;
        else b=new treap(xtag,v);
        now->root=merge(merge(a,b),c);
        now->g=now->root->g;
        return;
    }
    if(my<=mid)modify(now->l,l    ,mid,xtag,my,v);
    else       modify(now->r,mid+1,r  ,xtag,my,v);
    now->pull();
}
void modify(nodex *&now,int l,int r,int mx,int my,ll v){
    if(!now)now=new nodex();
    modify(now->root,0,y-1,mx,my,v);
    if(l==r)return;
    if(mx<=mid)modify(now->l,l    ,mid,mx,my,v);
    else       modify(now->r,mid+1,r  ,mx,my,v);
}
void update(int p, int q, long long v){
    modify(root,0,x-1,p,q,v);
}

ll query(nodey *now,int l,int r,int yl,int yr){
    if(yr<l || r<yl || !now)return 0;
    if(yl<=l&&r<=yr)return now->g;
    return gcd(query(now->l,l    ,mid,yl,yr),
               query(now->r,mid+1,r  ,yl,yr));
}
ll query(nodex *now,int l,int r,int xl,int xr,int yl,int yr){
    // cout<<"querying x range "<<l<<" to "<<r<<" , xl and xr: "<<xl<<" "<<xr<<endl;
    if(xr<l || r<xl || !now)return 0;
    if(xl<=l&&r<=xr){
        ll Q=query(now->root,0,y-1,yl,yr);
        // cout<<"x range "<<l<<" to "<<r<<" query "<<yl<<" to "<<yr<<" get "<<Q<<endl;
        return Q;
    }
    return gcd(query(now->l,l    ,mid,xl,xr,yl,yr),
               query(now->r,mid+1,r  ,xl,xr,yl,yr));
}
long long calculate(int x1, int y1, int x2, int y2){
    return query(root,0,x-1,x1,x2,y1,y2);
}

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;
      ^~~
game.cpp: In function 'treap* merge(treap*, treap*)':
game.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
game.cpp:22:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(!a)return b; if(!b)return a;
                     ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 4 ms 676 KB Output is correct
4 Correct 4 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 704 KB Output is correct
10 Correct 3 ms 704 KB Output is correct
11 Correct 3 ms 704 KB Output is correct
12 Correct 2 ms 704 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 3 ms 704 KB Output is correct
4 Correct 1169 ms 19032 KB Output is correct
5 Correct 720 ms 19456 KB Output is correct
6 Correct 902 ms 19456 KB Output is correct
7 Correct 1298 ms 19456 KB Output is correct
8 Correct 698 ms 19456 KB Output is correct
9 Correct 1280 ms 19456 KB Output is correct
10 Correct 1153 ms 19456 KB Output is correct
11 Correct 2 ms 19456 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19456 KB Output is correct
2 Correct 3 ms 19456 KB Output is correct
3 Correct 4 ms 19456 KB Output is correct
4 Correct 3 ms 19456 KB Output is correct
5 Correct 3 ms 19456 KB Output is correct
6 Correct 3 ms 19456 KB Output is correct
7 Correct 3 ms 19456 KB Output is correct
8 Correct 2 ms 19456 KB Output is correct
9 Correct 4 ms 19456 KB Output is correct
10 Correct 3 ms 19456 KB Output is correct
11 Correct 3 ms 19456 KB Output is correct
12 Correct 1966 ms 28224 KB Output is correct
13 Correct 3248 ms 28224 KB Output is correct
14 Correct 536 ms 28224 KB Output is correct
15 Correct 3849 ms 31456 KB Output is correct
16 Correct 400 ms 51488 KB Output is correct
17 Correct 2190 ms 51488 KB Output is correct
18 Correct 3953 ms 61888 KB Output is correct
19 Correct 3282 ms 67496 KB Output is correct
20 Correct 2844 ms 72120 KB Output is correct
21 Correct 3 ms 72120 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 72120 KB Output is correct
2 Correct 4 ms 72120 KB Output is correct
3 Correct 3 ms 72120 KB Output is correct
4 Correct 3 ms 72120 KB Output is correct
5 Correct 2 ms 72120 KB Output is correct
6 Correct 2 ms 72120 KB Output is correct
7 Correct 3 ms 72120 KB Output is correct
8 Correct 3 ms 72120 KB Output is correct
9 Correct 3 ms 72120 KB Output is correct
10 Correct 3 ms 72120 KB Output is correct
11 Correct 4 ms 72120 KB Output is correct
12 Correct 1008 ms 72120 KB Output is correct
13 Correct 830 ms 72120 KB Output is correct
14 Correct 1070 ms 72120 KB Output is correct
15 Correct 1270 ms 72120 KB Output is correct
16 Correct 800 ms 72120 KB Output is correct
17 Correct 1196 ms 72120 KB Output is correct
18 Correct 1162 ms 72120 KB Output is correct
19 Correct 1886 ms 72120 KB Output is correct
20 Correct 3426 ms 72120 KB Output is correct
21 Correct 498 ms 72120 KB Output is correct
22 Correct 3854 ms 72120 KB Output is correct
23 Correct 392 ms 90924 KB Output is correct
24 Correct 1969 ms 90924 KB Output is correct
25 Correct 3612 ms 101340 KB Output is correct
26 Correct 3351 ms 106928 KB Output is correct
27 Correct 3173 ms 111680 KB Output is correct
28 Runtime error 2945 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -