oj.uz

Submission #13372

# Submission time Handle Problem Language Result Execution time Memory
13372 2015-02-14T04:37:45 Z dohyun0324 Game (IOI13_game) C++
63 / 100
 3430 ms 256000 KB 
#include<stdio.h>
#include "game.h"
typedef long long ll;
int n,m,x1,y1,x2,y2;
ll k;
ll gcd2(ll X, ll Y) {
    if(X==0) return Y; if(Y==0) return X;
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct data
{
    int rs,re;
    data *l,*r;
    data(){}
    data(int s,int e):rs(s),re(e){l=r=NULL;}
    void update3(int rx,int ry)
    {
        if(rx==ry){start2.update2(1,m); return;}
        int mid=(rx+ry)/2;
        if(x1<=mid)
        {
            if(l==NULL) l=new data(rx,mid);
            l->update3(rx,mid);
        }
        else
        {
            if(r==NULL) r=new data(mid+1,ry);
            r->update3(mid+1,ry);
        }
        x2=y1; y2=y1;
        if(r==NULL) k=l->start2.query2(1,m);
        else if(l==NULL) k=r->start2.query2(1,m);
        else k=gcd2(l->start2.query2(1,m),r->start2.query2(1,m));
        start2.update2(1,m);
    }
    ll query(int rx,int ry)
    {
        int mid=(rx+ry)/2;
        if(x1<=rx && ry<=y1) return start2.query2(1,m);
        if(x1>ry || y1<rx) return 0;
        if(l==NULL && r==NULL) return 0;
        else if(l==NULL) return r->query(mid+1,ry);
        else if(r==NULL) return l->query(rx,mid);
        return gcd2(l->query(rx,mid),r->query(mid+1,ry));
    }
    struct data2
    {
        int cs,ce; ll val;
        data2 *l,*r;
        data2(){}
        data2(int s,int e,ll v):cs(s),ce(e),val(v){l=r=NULL;}
        void update2(int cx,int cy)
        {
            if(cx==cy){val=k; return;}
            int mid=(cx+cy)/2;
            if(y1<=mid){
                if(l==NULL) l=new data2(cx,mid,0);
                l->update2(cx,mid);
            }
            else{
                if(r==NULL) r=new data2(mid+1,cy,0);
                r->update2(mid+1,cy);
            }
            if(r==NULL) val=l->val;
            else if(l==NULL) val=r->val;
            else val=gcd2(l->val,r->val);
        }
        ll query2(int cx,int cy)
        {
            int mid=(cx+cy)/2;
            if(cx>y2 || cy<x2) return 0;
            if((x2<=cx && cy<=y2) || (l==NULL && r==NULL)) return val;
            if(l==NULL) return r->query2(mid+1,cy);
            else if(r==NULL) return l->query2(cx,mid);
            return gcd2(l->query2(cx,mid),r->query2(mid+1,cy));
        }
    };
    data2 start2=data2(1,m,0);
};
void init(int R, int C){
    n=R+1, m=C+1;
}
data start=data(1,n);
void update(int P, int Q, ll K){
    P++; Q++;
    x1=P; y1=Q; k=K;
    start.update3(1,n);
}
ll calculate(int P, int Q, int U, int V){
    x1=P+1; y1=U+1; x2=Q+1; y2=V+1;
    return start.query(1,n);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1256 KB Output is correct
2 Correct 0 ms 1388 KB Output is correct
3 Correct 1 ms 1388 KB Output is correct
4 Correct 0 ms 1256 KB Output is correct
5 Correct 0 ms 1256 KB Output is correct
6 Correct 0 ms 1388 KB Output is correct
7 Correct 0 ms 1256 KB Output is correct
8 Correct 0 ms 1256 KB Output is correct
9 Correct 0 ms 1388 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct
12 Correct 0 ms 1256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1256 KB Output is correct
2 Correct 0 ms 1256 KB Output is correct
3 Correct 0 ms 1256 KB Output is correct
4 Correct 761 ms 14192 KB Output is correct
5 Correct 554 ms 14192 KB Output is correct
6 Correct 816 ms 14456 KB Output is correct
7 Correct 957 ms 14456 KB Output is correct
8 Correct 623 ms 8648 KB Output is correct
9 Correct 902 ms 14588 KB Output is correct
10 Correct 768 ms 14456 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1256 KB Output is correct
2 Correct 0 ms 1388 KB Output is correct
3 Correct 1 ms 1388 KB Output is correct
4 Correct 0 ms 1256 KB Output is correct
5 Correct 0 ms 1256 KB Output is correct
6 Correct 1 ms 1388 KB Output is correct
7 Correct 0 ms 1256 KB Output is correct
8 Correct 0 ms 1256 KB Output is correct
9 Correct 0 ms 1388 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct
12 Correct 1269 ms 18284 KB Output is correct
13 Correct 2978 ms 8912 KB Output is correct
14 Correct 390 ms 1388 KB Output is correct
15 Correct 3430 ms 12608 KB Output is correct
16 Correct 1079 ms 26864 KB Output is correct
17 Correct 1394 ms 15908 KB Output is correct
18 Correct 2320 ms 26864 KB Output is correct
19 Correct 2069 ms 26864 KB Output is correct
20 Correct 1840 ms 26864 KB Output is correct
21 Correct 0 ms 1256 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1256 KB Output is correct
2 Correct 1 ms 1388 KB Output is correct
3 Correct 1 ms 1388 KB Output is correct
4 Correct 0 ms 1256 KB Output is correct
5 Correct 0 ms 1256 KB Output is correct
6 Correct 0 ms 1388 KB Output is correct
7 Correct 0 ms 1256 KB Output is correct
8 Correct 0 ms 1256 KB Output is correct
9 Correct 1 ms 1388 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct
12 Correct 746 ms 14192 KB Output is correct
13 Correct 535 ms 14192 KB Output is correct
14 Correct 823 ms 14456 KB Output is correct
15 Correct 899 ms 14456 KB Output is correct
16 Correct 609 ms 8648 KB Output is correct
17 Correct 876 ms 14588 KB Output is correct
18 Correct 747 ms 14456 KB Output is correct
19 Correct 1249 ms 18284 KB Output is correct
20 Correct 3018 ms 8912 KB Output is correct
21 Correct 384 ms 1388 KB Output is correct
22 Correct 3278 ms 12608 KB Output is correct
23 Correct 1124 ms 26864 KB Output is correct
24 Correct 1455 ms 15908 KB Output is correct
25 Correct 2340 ms 26864 KB Output is correct
26 Correct 2022 ms 26864 KB Output is correct
27 Correct 1848 ms 26864 KB Output is correct
28 Memory limit exceeded 716 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1256 KB Output is correct
2 Correct 0 ms 1388 KB Output is correct
3 Correct 0 ms 1388 KB Output is correct
4 Correct 0 ms 1256 KB Output is correct
5 Correct 0 ms 1256 KB Output is correct
6 Correct 0 ms 1388 KB Output is correct
7 Correct 0 ms 1256 KB Output is correct
8 Correct 0 ms 1256 KB Output is correct
9 Correct 1 ms 1388 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct
12 Correct 746 ms 14192 KB Output is correct
13 Correct 512 ms 14192 KB Output is correct
14 Correct 829 ms 14456 KB Output is correct
15 Correct 910 ms 14456 KB Output is correct
16 Correct 618 ms 8648 KB Output is correct
17 Correct 894 ms 14588 KB Output is correct
18 Correct 741 ms 14456 KB Output is correct
19 Correct 1274 ms 18284 KB Output is correct
20 Correct 3001 ms 8912 KB Output is correct
21 Correct 368 ms 1388 KB Output is correct
22 Correct 3384 ms 12608 KB Output is correct
23 Correct 1094 ms 26864 KB Output is correct
24 Correct 1386 ms 15908 KB Output is correct
25 Correct 2284 ms 26864 KB Output is correct
26 Correct 2024 ms 26864 KB Output is correct
27 Correct 1848 ms 26864 KB Output is correct
28 Memory limit exceeded 679 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -