oj.uz

Submission #65478

# Submission time Handle Problem Language Result Execution time Memory
65478 2018-08-07T16:41:39 Z edisonhello Game (IOI13_game) C++14
63 / 100
 3916 ms 215432 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 3 ms 484 KB Output is correct
3 Correct 3 ms 688 KB Output is correct
4 Correct 2 ms 688 KB Output is correct
5 Correct 4 ms 688 KB Output is correct
6 Correct 3 ms 688 KB Output is correct
7 Correct 3 ms 688 KB Output is correct
8 Correct 2 ms 688 KB Output is correct
9 Correct 3 ms 732 KB Output is correct
10 Correct 3 ms 732 KB Output is correct
11 Correct 3 ms 732 KB Output is correct
12 Correct 3 ms 732 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 732 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Correct 1170 ms 12232 KB Output is correct
5 Correct 786 ms 12716 KB Output is correct
6 Correct 1027 ms 12716 KB Output is correct
7 Correct 1095 ms 12716 KB Output is correct
8 Correct 736 ms 12716 KB Output is correct
9 Correct 1133 ms 12716 KB Output is correct
10 Correct 926 ms 12716 KB Output is correct
11 Correct 3 ms 12716 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12716 KB Output is correct
2 Correct 4 ms 12716 KB Output is correct
3 Correct 5 ms 12716 KB Output is correct
4 Correct 3 ms 12716 KB Output is correct
5 Correct 3 ms 12716 KB Output is correct
6 Correct 4 ms 12716 KB Output is correct
7 Correct 3 ms 12716 KB Output is correct
8 Correct 3 ms 12716 KB Output is correct
9 Correct 3 ms 12716 KB Output is correct
10 Correct 3 ms 12716 KB Output is correct
11 Correct 3 ms 12716 KB Output is correct
12 Correct 1919 ms 18056 KB Output is correct
13 Correct 3439 ms 18056 KB Output is correct
14 Correct 490 ms 18056 KB Output is correct
15 Correct 3916 ms 24428 KB Output is correct
16 Correct 339 ms 34484 KB Output is correct
17 Correct 1896 ms 34484 KB Output is correct
18 Correct 3206 ms 34968 KB Output is correct
19 Correct 2780 ms 35204 KB Output is correct
20 Correct 2554 ms 35204 KB Output is correct
21 Correct 2 ms 35204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 35204 KB Output is correct
2 Correct 3 ms 35204 KB Output is correct
3 Correct 3 ms 35204 KB Output is correct
4 Correct 3 ms 35204 KB Output is correct
5 Correct 3 ms 35204 KB Output is correct
6 Correct 3 ms 35204 KB Output is correct
7 Correct 2 ms 35204 KB Output is correct
8 Correct 3 ms 35204 KB Output is correct
9 Correct 2 ms 35204 KB Output is correct
10 Correct 4 ms 35204 KB Output is correct
11 Correct 3 ms 35204 KB Output is correct
12 Correct 1209 ms 35204 KB Output is correct
13 Correct 823 ms 35204 KB Output is correct
14 Correct 1002 ms 35204 KB Output is correct
15 Correct 1176 ms 35204 KB Output is correct
16 Correct 703 ms 35204 KB Output is correct
17 Correct 1063 ms 35204 KB Output is correct
18 Correct 936 ms 35204 KB Output is correct
19 Correct 1924 ms 35204 KB Output is correct
20 Correct 3440 ms 35204 KB Output is correct
21 Correct 570 ms 35204 KB Output is correct
22 Correct 3863 ms 35204 KB Output is correct
23 Correct 394 ms 35204 KB Output is correct
24 Correct 1874 ms 35204 KB Output is correct
25 Correct 3168 ms 35204 KB Output is correct
26 Correct 2935 ms 35204 KB Output is correct
27 Correct 2673 ms 35204 KB Output is correct
28 Execution timed out 1147 ms 207912 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 207912 KB Output is correct
2 Correct 4 ms 207912 KB Output is correct
3 Correct 4 ms 207912 KB Output is correct
4 Correct 4 ms 207912 KB Output is correct
5 Correct 3 ms 207912 KB Output is correct
6 Correct 4 ms 207912 KB Output is correct
7 Correct 3 ms 207912 KB Output is correct
8 Correct 2 ms 207912 KB Output is correct
9 Correct 3 ms 207912 KB Output is correct
10 Correct 3 ms 207912 KB Output is correct
11 Correct 3 ms 207912 KB Output is correct
12 Correct 997 ms 207912 KB Output is correct
13 Correct 720 ms 207912 KB Output is correct
14 Correct 983 ms 207912 KB Output is correct
15 Correct 1172 ms 207912 KB Output is correct
16 Correct 719 ms 207912 KB Output is correct
17 Correct 1147 ms 207912 KB Output is correct
18 Correct 944 ms 207912 KB Output is correct
19 Correct 1709 ms 207912 KB Output is correct
20 Correct 3106 ms 207912 KB Output is correct
21 Correct 510 ms 207912 KB Output is correct
22 Correct 3509 ms 207912 KB Output is correct
23 Correct 349 ms 207912 KB Output is correct
24 Correct 1887 ms 207912 KB Output is correct
25 Correct 2895 ms 207912 KB Output is correct
26 Correct 2789 ms 207912 KB Output is correct
27 Correct 2435 ms 207912 KB Output is correct
28 Execution timed out 1411 ms 215432 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -