oj.uz

Submission #13373

# Submission time Handle Problem Language Result Execution time Memory
13373 2015-02-14T04:42:09 Z dohyun0324 Game (IOI13_game) C++
63 / 100
 3405 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 1 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 0 ms 1388 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 1 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 754 ms 14192 KB Output is correct
5 Correct 519 ms 14192 KB Output is correct
6 Correct 837 ms 14456 KB Output is correct
7 Correct 897 ms 14456 KB Output is correct
8 Correct 593 ms 8648 KB Output is correct
9 Correct 910 ms 14588 KB Output is correct
10 Correct 754 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 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 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 1255 ms 18284 KB Output is correct
13 Correct 2993 ms 8912 KB Output is correct
14 Correct 372 ms 1388 KB Output is correct
15 Correct 3405 ms 12608 KB Output is correct
16 Correct 1070 ms 26864 KB Output is correct
17 Correct 1385 ms 15908 KB Output is correct
18 Correct 2334 ms 26864 KB Output is correct
19 Correct 2093 ms 26864 KB Output is correct
20 Correct 1849 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 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 743 ms 14192 KB Output is correct
13 Correct 499 ms 14192 KB Output is correct
14 Correct 804 ms 14456 KB Output is correct
15 Correct 909 ms 14456 KB Output is correct
16 Correct 605 ms 8648 KB Output is correct
17 Correct 867 ms 14588 KB Output is correct
18 Correct 761 ms 14456 KB Output is correct
19 Correct 1258 ms 18284 KB Output is correct
20 Correct 2992 ms 8912 KB Output is correct
21 Correct 377 ms 1388 KB Output is correct
22 Correct 3309 ms 12608 KB Output is correct
23 Correct 1113 ms 26864 KB Output is correct
24 Correct 1403 ms 15908 KB Output is correct
25 Correct 2331 ms 26864 KB Output is correct
26 Correct 1934 ms 26864 KB Output is correct
27 Correct 1841 ms 26864 KB Output is correct
28 Memory limit exceeded 743 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 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 737 ms 14192 KB Output is correct
13 Correct 516 ms 14192 KB Output is correct
14 Correct 819 ms 14456 KB Output is correct
15 Correct 942 ms 14456 KB Output is correct
16 Correct 614 ms 8648 KB Output is correct
17 Correct 904 ms 14588 KB Output is correct
18 Correct 781 ms 14456 KB Output is correct
19 Correct 1267 ms 18284 KB Output is correct
20 Correct 2983 ms 8912 KB Output is correct
21 Correct 358 ms 1388 KB Output is correct
22 Correct 3376 ms 12608 KB Output is correct
23 Correct 1092 ms 26864 KB Output is correct
24 Correct 1407 ms 15908 KB Output is correct
25 Correct 2302 ms 26864 KB Output is correct
26 Correct 2043 ms 26864 KB Output is correct
27 Correct 1871 ms 26864 KB Output is correct
28 Memory limit exceeded 637 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -