oj.uz

Submission #13371

# Submission time Handle Problem Language Result Execution time Memory
13371 2015-02-14T04:28:26 Z dohyun0324 Game (IOI13_game) C++
63 / 100
 3393 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) l=new data(rx,mid);
        if(r==NULL) r=new data(mid+1,ry);
        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) {
    P++; Q++; U++; V++;
    x1=P; y1=U; x2=Q; y2=V;
    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 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 697 ms 14192 KB Output is correct
5 Correct 508 ms 14192 KB Output is correct
6 Correct 783 ms 14456 KB Output is correct
7 Correct 902 ms 14456 KB Output is correct
8 Correct 604 ms 8648 KB Output is correct
9 Correct 893 ms 14588 KB Output is correct
10 Correct 725 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 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 1 ms 1256 KB Output is correct
11 Correct 1 ms 1256 KB Output is correct
12 Correct 1209 ms 18284 KB Output is correct
13 Correct 2960 ms 8912 KB Output is correct
14 Correct 426 ms 1388 KB Output is correct
15 Correct 3330 ms 12608 KB Output is correct
16 Correct 1098 ms 26864 KB Output is correct
17 Correct 1383 ms 15908 KB Output is correct
18 Correct 2195 ms 26864 KB Output is correct
19 Correct 1949 ms 26864 KB Output is correct
20 Correct 1730 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 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 715 ms 14192 KB Output is correct
13 Correct 522 ms 14192 KB Output is correct
14 Correct 803 ms 14456 KB Output is correct
15 Correct 897 ms 14456 KB Output is correct
16 Correct 561 ms 8648 KB Output is correct
17 Correct 860 ms 14588 KB Output is correct
18 Correct 706 ms 14456 KB Output is correct
19 Correct 1211 ms 18284 KB Output is correct
20 Correct 2922 ms 8912 KB Output is correct
21 Correct 387 ms 1388 KB Output is correct
22 Correct 3366 ms 12608 KB Output is correct
23 Correct 1095 ms 26864 KB Output is correct
24 Correct 1350 ms 15908 KB Output is correct
25 Correct 2152 ms 26864 KB Output is correct
26 Correct 1920 ms 26864 KB Output is correct
27 Correct 1761 ms 26864 KB Output is correct
28 Memory limit exceeded 464 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 725 ms 14192 KB Output is correct
13 Correct 528 ms 14192 KB Output is correct
14 Correct 823 ms 14456 KB Output is correct
15 Correct 924 ms 14456 KB Output is correct
16 Correct 572 ms 8648 KB Output is correct
17 Correct 879 ms 14588 KB Output is correct
18 Correct 744 ms 14456 KB Output is correct
19 Correct 1210 ms 18284 KB Output is correct
20 Correct 2980 ms 8912 KB Output is correct
21 Correct 392 ms 1388 KB Output is correct
22 Correct 3393 ms 12608 KB Output is correct
23 Correct 1103 ms 26864 KB Output is correct
24 Correct 1356 ms 15908 KB Output is correct
25 Correct 2227 ms 26864 KB Output is correct
26 Correct 2018 ms 26864 KB Output is correct
27 Correct 1777 ms 26864 KB Output is correct
28 Memory limit exceeded 444 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -