oj.uz

Submission #65453

# Submission time Handle Problem Language Result Execution time Memory
65453 2018-08-07T15:57:28 Z edisonhello Game (IOI13_game) C++14
63 / 100
 4179 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,xpool[30*25000];
nodex *getnodex(){
    static int ptr=-1;
    return &xpool[++ptr];
}

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=getnodex();
    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 15 ms 17912 KB Output is correct
2 Correct 19 ms 18148 KB Output is correct
3 Correct 18 ms 18224 KB Output is correct
4 Correct 16 ms 18224 KB Output is correct
5 Correct 17 ms 18224 KB Output is correct
6 Correct 18 ms 18336 KB Output is correct
7 Correct 17 ms 18336 KB Output is correct
8 Correct 17 ms 18336 KB Output is correct
9 Correct 17 ms 18336 KB Output is correct
10 Correct 18 ms 18336 KB Output is correct
11 Correct 18 ms 18344 KB Output is correct
12 Correct 20 ms 18344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 18344 KB Output is correct
2 Correct 16 ms 18344 KB Output is correct
3 Correct 16 ms 18344 KB Output is correct
4 Correct 1058 ms 36692 KB Output is correct
5 Correct 859 ms 37116 KB Output is correct
6 Correct 1075 ms 37116 KB Output is correct
7 Correct 1259 ms 37116 KB Output is correct
8 Correct 803 ms 37116 KB Output is correct
9 Correct 1213 ms 37116 KB Output is correct
10 Correct 994 ms 37116 KB Output is correct
11 Correct 15 ms 37116 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37116 KB Output is correct
2 Correct 18 ms 37116 KB Output is correct
3 Correct 18 ms 37116 KB Output is correct
4 Correct 17 ms 37116 KB Output is correct
5 Correct 16 ms 37116 KB Output is correct
6 Correct 17 ms 37116 KB Output is correct
7 Correct 17 ms 37116 KB Output is correct
8 Correct 18 ms 37116 KB Output is correct
9 Correct 18 ms 37116 KB Output is correct
10 Correct 20 ms 37116 KB Output is correct
11 Correct 20 ms 37116 KB Output is correct
12 Correct 1977 ms 45896 KB Output is correct
13 Correct 3343 ms 45896 KB Output is correct
14 Correct 553 ms 45896 KB Output is correct
15 Correct 3826 ms 49088 KB Output is correct
16 Correct 468 ms 68992 KB Output is correct
17 Correct 2198 ms 68992 KB Output is correct
18 Correct 4179 ms 79528 KB Output is correct
19 Correct 3443 ms 85068 KB Output is correct
20 Correct 3068 ms 89572 KB Output is correct
21 Correct 16 ms 89572 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 89572 KB Output is correct
2 Correct 17 ms 89572 KB Output is correct
3 Correct 18 ms 89572 KB Output is correct
4 Correct 15 ms 89572 KB Output is correct
5 Correct 17 ms 89572 KB Output is correct
6 Correct 17 ms 89572 KB Output is correct
7 Correct 18 ms 89572 KB Output is correct
8 Correct 16 ms 89572 KB Output is correct
9 Correct 16 ms 89572 KB Output is correct
10 Correct 18 ms 89572 KB Output is correct
11 Correct 17 ms 89572 KB Output is correct
12 Correct 1152 ms 89572 KB Output is correct
13 Correct 718 ms 89572 KB Output is correct
14 Correct 1066 ms 89572 KB Output is correct
15 Correct 1181 ms 89572 KB Output is correct
16 Correct 702 ms 89572 KB Output is correct
17 Correct 1158 ms 89572 KB Output is correct
18 Correct 1057 ms 89572 KB Output is correct
19 Correct 1821 ms 89572 KB Output is correct
20 Correct 3166 ms 89572 KB Output is correct
21 Correct 552 ms 89572 KB Output is correct
22 Correct 3814 ms 89572 KB Output is correct
23 Correct 405 ms 108472 KB Output is correct
24 Correct 2113 ms 108472 KB Output is correct
25 Correct 3695 ms 118948 KB Output is correct
26 Correct 3344 ms 119048 KB Output is correct
27 Correct 2947 ms 119048 KB Output is correct
28 Runtime error 2540 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 15 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 -