oj.uz

Submission #65479

# Submission time Handle Problem Language Result Execution time Memory
65479 2018-08-07T16:44:00 Z edisonhello Game (IOI13_game) C++14
63 / 100
 4582 ms 191456 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{
    int l,r;
    ll v,g;
    int pri,key;
    void pull();
    // treap(int x,ll v):l(0),r(0),v(v),g(v),pri(rand()),key(x){}
} ts[30*10000];
void treap::pull(){ g=gcd(gcd(l?ts[l].g:0,r?ts[r].g:0),v); }
int gettreap(int x,ll v){
    static int ptr=1;
    ts[ptr].key=x;
    ts[ptr].v=ts[ptr].g=v;
    return ptr++;
}

int merge(int a,int b){
    if(!a)return b; if(!b)return a;
    if(ts[a].pri>ts[b].pri){
        ts[a].r=merge(ts[a].r,b);
        ts[a].pull();
        return a;
    }
    else{
        ts[b].l=merge(a,ts[b].l);
        ts[b].pull();
        return b;
    }
}
void split(int now,int key,int &a,int &b){
    if(!now){ a=b=0; return; }
    if(ts[now].key<=key){
        a=now;
        split(ts[now].r,key,ts[a].r,b);
        ts[a].pull();
    }
    else{
        b=now;
        split(ts[now].l,key,a,ts[b].l);
        ts[b].pull();
    }
}
 
struct nodey{
    int l,r,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){
        int a,b,c,d;
        split(ys[now].root,xtag-1,a,d);
        split(d,xtag,b,c);
        if(b)ts[b].v=ts[b].g=v;
        else b=gettreap(xtag,v);
        ys[now].root=merge(merge(a,b),c);
        ys[now].g=ts[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 'int merge(int, int)':
game.cpp:30:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
game.cpp:30: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 2 ms 248 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 954 ms 12152 KB Output is correct
5 Correct 764 ms 12632 KB Output is correct
6 Correct 988 ms 12632 KB Output is correct
7 Correct 1063 ms 12632 KB Output is correct
8 Correct 658 ms 12632 KB Output is correct
9 Correct 1067 ms 12632 KB Output is correct
10 Correct 963 ms 12632 KB Output is correct
11 Correct 3 ms 12632 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Correct 3 ms 12632 KB Output is correct
9 Correct 4 ms 12632 KB Output is correct
10 Correct 3 ms 12632 KB Output is correct
11 Correct 3 ms 12632 KB Output is correct
12 Correct 1769 ms 16868 KB Output is correct
13 Correct 3280 ms 16868 KB Output is correct
14 Correct 537 ms 16868 KB Output is correct
15 Correct 3889 ms 16868 KB Output is correct
16 Correct 374 ms 18116 KB Output is correct
17 Correct 1978 ms 18116 KB Output is correct
18 Correct 3407 ms 18424 KB Output is correct
19 Correct 2980 ms 18536 KB Output is correct
20 Correct 2841 ms 18536 KB Output is correct
21 Correct 3 ms 18536 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18536 KB Output is correct
2 Correct 3 ms 18536 KB Output is correct
3 Correct 4 ms 18536 KB Output is correct
4 Correct 3 ms 18536 KB Output is correct
5 Correct 4 ms 18536 KB Output is correct
6 Correct 3 ms 18536 KB Output is correct
7 Correct 3 ms 18536 KB Output is correct
8 Correct 3 ms 18536 KB Output is correct
9 Correct 3 ms 18536 KB Output is correct
10 Correct 4 ms 18536 KB Output is correct
11 Correct 4 ms 18536 KB Output is correct
12 Correct 1280 ms 18536 KB Output is correct
13 Correct 808 ms 18536 KB Output is correct
14 Correct 1191 ms 18536 KB Output is correct
15 Correct 1278 ms 18536 KB Output is correct
16 Correct 762 ms 18536 KB Output is correct
17 Correct 1255 ms 18536 KB Output is correct
18 Correct 1184 ms 18536 KB Output is correct
19 Correct 2061 ms 18536 KB Output is correct
20 Correct 3601 ms 18536 KB Output is correct
21 Correct 585 ms 18536 KB Output is correct
22 Correct 4582 ms 18536 KB Output is correct
23 Correct 391 ms 18536 KB Output is correct
24 Correct 2112 ms 18536 KB Output is correct
25 Correct 3846 ms 18536 KB Output is correct
26 Correct 3172 ms 18736 KB Output is correct
27 Correct 2814 ms 18736 KB Output is correct
28 Execution timed out 1183 ms 191456 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 191456 KB Output is correct
2 Correct 4 ms 191456 KB Output is correct
3 Correct 5 ms 191456 KB Output is correct
4 Correct 2 ms 191456 KB Output is correct
5 Correct 3 ms 191456 KB Output is correct
6 Correct 3 ms 191456 KB Output is correct
7 Correct 2 ms 191456 KB Output is correct
8 Correct 3 ms 191456 KB Output is correct
9 Correct 3 ms 191456 KB Output is correct
10 Correct 3 ms 191456 KB Output is correct
11 Correct 3 ms 191456 KB Output is correct
12 Correct 1238 ms 191456 KB Output is correct
13 Correct 842 ms 191456 KB Output is correct
14 Correct 1103 ms 191456 KB Output is correct
15 Correct 1223 ms 191456 KB Output is correct
16 Correct 769 ms 191456 KB Output is correct
17 Correct 1245 ms 191456 KB Output is correct
18 Correct 1066 ms 191456 KB Output is correct
19 Correct 2086 ms 191456 KB Output is correct
20 Correct 3524 ms 191456 KB Output is correct
21 Correct 587 ms 191456 KB Output is correct
22 Correct 4436 ms 191456 KB Output is correct
23 Correct 425 ms 191456 KB Output is correct
24 Correct 2201 ms 191456 KB Output is correct
25 Correct 3688 ms 191456 KB Output is correct
26 Correct 3173 ms 191456 KB Output is correct
27 Correct 3065 ms 191456 KB Output is correct
28 Execution timed out 1531 ms 191456 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -