oj.uz

Submission #65473

# Submission time Handle Problem Language Result Execution time Memory
65473 2018-08-07T16:30:31 Z edisonhello Game (IOI13_game) C++14
63 / 100
 3951 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{
    int l,r;
    treap *root;
    ll g;
    void pull();
    // void pull(){ g=gcd(l?l->g:0,r?r->g:0); return; }
} ys[30*30*10000];

void nodey::pull(){ g=gcd(l?ys[l].g:0,r?ys[r].g:0); }
 
struct nodex{
    int l,r,root;
} xs[30*10000];
int root,xptr,yptr;
 
int x,y;
 
void init(int R, int C){
    x=R; y=C;
}
 
#define mid ((l+r)>>1)
void modifyy(int &now,int l,int r,int xtag,int my,ll v){
    if(!now)now=++yptr;
    if(l==r){
        treap *a,*b,*c,*d;
        split(ys[now].root,xtag-1,a,d);
        split(d,xtag,b,c);
        if(b)b->v=b->g=v;
        else b=new treap(xtag,v);
        ys[now].root=merge(merge(a,b),c);
        ys[now].g=ys[now].root->g;
        return;
    }
    if(my<=mid)modifyy(ys[now].l,l    ,mid,xtag,my,v);
    else       modifyy(ys[now].r,mid+1,r  ,xtag,my,v);
    ys[now].pull();
}
void modifyx(int &now,int l,int r,int mx,int my,ll v){
    if(!now)now=++xptr;
    modifyy(xs[now].root,0,y-1,mx,my,v);
    if(l==r)return;
    if(mx<=mid)modifyx(xs[now].l,l    ,mid,mx,my,v);
    else       modifyx(xs[now].r,mid+1,r  ,mx,my,v);
}
void update(int p, int q, long long v){
    modifyx(root,0,x-1,p,q,v);
}
 
ll query(int now,int l,int r,int yl,int yr){
    if(yr<l || r<yl || !now)return 0;
    if(yl<=l&&r<=yr)return ys[now].g;
    return gcd(query(ys[now].l,l    ,mid,yl,yr),
               query(ys[now].r,mid+1,r  ,yl,yr));
}
ll query(int 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(xs[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(xs[now].l,l    ,mid,xl,xr,yl,yr),
               query(xs[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 248 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 612 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 4 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 3 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 3 ms 672 KB Output is correct
12 Correct 4 ms 672 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 672 KB Output is correct
2 Correct 2 ms 672 KB Output is correct
3 Correct 3 ms 672 KB Output is correct
4 Correct 1101 ms 12916 KB Output is correct
5 Correct 812 ms 13184 KB Output is correct
6 Correct 959 ms 13184 KB Output is correct
7 Correct 1134 ms 13184 KB Output is correct
8 Correct 725 ms 13184 KB Output is correct
9 Correct 954 ms 13184 KB Output is correct
10 Correct 1033 ms 13184 KB Output is correct
11 Correct 2 ms 13184 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13184 KB Output is correct
2 Correct 3 ms 13184 KB Output is correct
3 Correct 3 ms 13184 KB Output is correct
4 Correct 3 ms 13184 KB Output is correct
5 Correct 3 ms 13184 KB Output is correct
6 Correct 4 ms 13184 KB Output is correct
7 Correct 2 ms 13184 KB Output is correct
8 Correct 2 ms 13184 KB Output is correct
9 Correct 3 ms 13184 KB Output is correct
10 Correct 3 ms 13184 KB Output is correct
11 Correct 3 ms 13184 KB Output is correct
12 Correct 1808 ms 19848 KB Output is correct
13 Correct 3153 ms 19848 KB Output is correct
14 Correct 612 ms 19848 KB Output is correct
15 Correct 3951 ms 25608 KB Output is correct
16 Correct 331 ms 38468 KB Output is correct
17 Correct 1583 ms 38468 KB Output is correct
18 Correct 3216 ms 49160 KB Output is correct
19 Correct 2364 ms 54528 KB Output is correct
20 Correct 2566 ms 59168 KB Output is correct
21 Correct 2 ms 59168 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 59168 KB Output is correct
2 Correct 3 ms 59168 KB Output is correct
3 Correct 3 ms 59168 KB Output is correct
4 Correct 3 ms 59168 KB Output is correct
5 Correct 2 ms 59168 KB Output is correct
6 Correct 3 ms 59168 KB Output is correct
7 Correct 3 ms 59168 KB Output is correct
8 Correct 3 ms 59168 KB Output is correct
9 Correct 3 ms 59168 KB Output is correct
10 Correct 3 ms 59168 KB Output is correct
11 Correct 3 ms 59168 KB Output is correct
12 Correct 1131 ms 59168 KB Output is correct
13 Correct 694 ms 59168 KB Output is correct
14 Correct 1064 ms 59168 KB Output is correct
15 Correct 1233 ms 59168 KB Output is correct
16 Correct 697 ms 59168 KB Output is correct
17 Correct 980 ms 59168 KB Output is correct
18 Correct 864 ms 59168 KB Output is correct
19 Correct 1720 ms 59168 KB Output is correct
20 Correct 3287 ms 59168 KB Output is correct
21 Correct 510 ms 59168 KB Output is correct
22 Correct 3925 ms 65000 KB Output is correct
23 Correct 351 ms 77772 KB Output is correct
24 Correct 1842 ms 77772 KB Output is correct
25 Correct 3432 ms 88432 KB Output is correct
26 Correct 2646 ms 88432 KB Output is correct
27 Correct 2566 ms 88432 KB Output is correct
28 Runtime error 1252 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 2 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 -