oj.uz

Submission #13386

# Submission time Handle Problem Language Result Execution time Memory
13386 2015-02-15T06:29:40 Z dohyun0324 Game (IOI13_game) C++
100 / 100
 7901 ms 70684 KB 
#include<stdio.h>
#include "game.h"
typedef long long ll;
int x4,y4,x3,y3,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;
}
void finding(int y1,int x,int y)
{
    int mi;
    x3=1; y3=m;
    while(1)
    {
        mi=(x3+y3)/2;
        if(y1<=mi) y3=mi;
        else x3=mi+1;
        if(x3<=x && y<=y3) x4=x3, y4=y3;
        else break;
    }
}
struct data
{
    data *l,*r;
    data(){l=r=NULL;}
    void update3(int rx,int ry)
    {
        if(rx==ry){start2.update2(); return;}
        int mid=(rx+ry)/2;
        if(x1<=mid)
        {
            if(l==NULL) l=new data();
            l->update3(rx,mid);
        }
        else
        {
            if(r==NULL) r=new data();
            r->update3(mid+1,ry);
        }
        x2=y1; y2=y1;
        if(r==NULL) k=l->start2.query2();
        else if(l==NULL) k=r->start2.query2();
        else k=gcd2(l->start2.query2(),r->start2.query2());
        start2.update2();
    }
    ll query(int rx,int ry)
    {
        int mid=(rx+ry)/2;
        if(x1<=rx && ry<=y1) return start2.query2();
        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
    {
        ll val;
        int cx,cy;
        data2 *l,*r;
        data2(){}
        data2(ll v,int cx,int cy):val(v),cx(cx),cy(cy){l=r=NULL;}
        void update2()
        {
            if(cy==0) cy=m;
            if(cx==cy){val=k; return;}
            int mid=(cx+cy)/2;
            if(y1<=mid){
                if(l==NULL) l=new data2(0,y1,y1);
                else if(y1<l->cx)
                {
                    data2 *p=l;
                    finding(y1,l->cx,l->cy);
                    l=new data2(0,x4,y4); l->r=p;
                    l->l=new data2(0,y1,y1);
                }
                else if(y1>l->cy)
                {
                    data2 *p=l;
                    finding(y1,l->cx,l->cy);
                    l=new data2(0,x4,y4); l->l=p;
                    l->r=new data2(0,y1,y1);
                }
                l->update2();
            }
            else{
                if(r==NULL) r=new data2(0,y1,y1);
                else if(y1<r->cx)
                {
                    data2 *p=r;
                    finding(y1,r->cx,r->cy);
                    r=new data2(0,x4,y4); r->r=p;
                    r->l=new data2(0,y1,y1);
                }
                else if(y1>r->cy)
                {
                    data2 *p=r;
                    finding(y1,r->cx,r->cy);
                    r=new data2(0,x4,y4); r->l=p;
                    r->r=new data2(0,y1,y1);
                }
                r->update2();
            }
            if(r==NULL) val=l->val;
            else if(l==NULL) val=r->val;
            else val=gcd2(l->val,r->val);
        }
        ll query2()
        {
            if(cy==0) cy=m;
            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();
            else if(r==NULL) return l->query2();
            return gcd2(l->query2(),r->query2());
        }
    };
    data2 start2=data2(0,1,m);
};
void init(int R, int C){
    n=R+1, m=C+1;
}
data start=data();
void update(int P, int Q, ll K){
    x1=P+1; y1=Q+1; 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 1252 KB Output is correct
2 Correct 1 ms 1252 KB Output is correct
3 Correct 1 ms 1252 KB Output is correct
4 Correct 0 ms 1252 KB Output is correct
5 Correct 0 ms 1252 KB Output is correct
6 Correct 1 ms 1252 KB Output is correct
7 Correct 0 ms 1252 KB Output is correct
8 Correct 0 ms 1252 KB Output is correct
9 Correct 0 ms 1252 KB Output is correct
10 Correct 0 ms 1252 KB Output is correct
11 Correct 1 ms 1252 KB Output is correct
12 Correct 0 ms 1252 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1252 KB Output is correct
2 Correct 0 ms 1252 KB Output is correct
3 Correct 0 ms 1252 KB Output is correct
4 Correct 682 ms 5476 KB Output is correct
5 Correct 497 ms 5344 KB Output is correct
6 Correct 759 ms 5344 KB Output is correct
7 Correct 863 ms 5344 KB Output is correct
8 Correct 525 ms 3232 KB Output is correct
9 Correct 865 ms 5476 KB Output is correct
10 Correct 716 ms 5476 KB Output is correct
11 Correct 0 ms 1252 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1252 KB Output is correct
2 Correct 0 ms 1252 KB Output is correct
3 Correct 0 ms 1252 KB Output is correct
4 Correct 0 ms 1252 KB Output is correct
5 Correct 0 ms 1252 KB Output is correct
6 Correct 0 ms 1252 KB Output is correct
7 Correct 0 ms 1252 KB Output is correct
8 Correct 0 ms 1252 KB Output is correct
9 Correct 0 ms 1252 KB Output is correct
10 Correct 0 ms 1252 KB Output is correct
11 Correct 1 ms 1252 KB Output is correct
12 Correct 1312 ms 8248 KB Output is correct
13 Correct 3263 ms 5080 KB Output is correct
14 Correct 302 ms 1252 KB Output is correct
15 Correct 3681 ms 6268 KB Output is correct
16 Correct 1031 ms 10096 KB Output is correct
17 Correct 1191 ms 5740 KB Output is correct
18 Correct 2081 ms 10096 KB Output is correct
19 Correct 1757 ms 10096 KB Output is correct
20 Correct 1605 ms 10096 KB Output is correct
21 Correct 0 ms 1252 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1252 KB Output is correct
2 Correct 0 ms 1252 KB Output is correct
3 Correct 0 ms 1252 KB Output is correct
4 Correct 0 ms 1252 KB Output is correct
5 Correct 0 ms 1252 KB Output is correct
6 Correct 0 ms 1252 KB Output is correct
7 Correct 0 ms 1252 KB Output is correct
8 Correct 0 ms 1252 KB Output is correct
9 Correct 0 ms 1252 KB Output is correct
10 Correct 0 ms 1252 KB Output is correct
11 Correct 0 ms 1252 KB Output is correct
12 Correct 692 ms 5476 KB Output is correct
13 Correct 492 ms 5344 KB Output is correct
14 Correct 762 ms 5344 KB Output is correct
15 Correct 892 ms 5344 KB Output is correct
16 Correct 511 ms 3232 KB Output is correct
17 Correct 824 ms 5476 KB Output is correct
18 Correct 735 ms 5476 KB Output is correct
19 Correct 1331 ms 8248 KB Output is correct
20 Correct 3247 ms 5080 KB Output is correct
21 Correct 304 ms 1252 KB Output is correct
22 Correct 3712 ms 6268 KB Output is correct
23 Correct 1033 ms 10096 KB Output is correct
24 Correct 1211 ms 5740 KB Output is correct
25 Correct 2067 ms 10096 KB Output is correct
26 Correct 1745 ms 10096 KB Output is correct
27 Correct 1595 ms 10096 KB Output is correct
28 Correct 615 ms 32932 KB Output is correct
29 Correct 2108 ms 32536 KB Output is correct
30 Correct 5631 ms 28576 KB Output is correct
31 Correct 5059 ms 21712 KB Output is correct
32 Correct 430 ms 1384 KB Output is correct
33 Correct 660 ms 1912 KB Output is correct
34 Correct 1310 ms 32536 KB Output is correct
35 Correct 1488 ms 16696 KB Output is correct
36 Correct 2811 ms 32536 KB Output is correct
37 Correct 2242 ms 32536 KB Output is correct
38 Correct 2167 ms 32536 KB Output is correct
39 Correct 1918 ms 25012 KB Output is correct
40 Correct 0 ms 1252 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1252 KB Output is correct
2 Correct 0 ms 1252 KB Output is correct
3 Correct 1 ms 1252 KB Output is correct
4 Correct 0 ms 1252 KB Output is correct
5 Correct 0 ms 1252 KB Output is correct
6 Correct 0 ms 1252 KB Output is correct
7 Correct 0 ms 1252 KB Output is correct
8 Correct 0 ms 1252 KB Output is correct
9 Correct 0 ms 1252 KB Output is correct
10 Correct 0 ms 1252 KB Output is correct
11 Correct 0 ms 1252 KB Output is correct
12 Correct 677 ms 5476 KB Output is correct
13 Correct 476 ms 5344 KB Output is correct
14 Correct 762 ms 5344 KB Output is correct
15 Correct 876 ms 5344 KB Output is correct
16 Correct 519 ms 3232 KB Output is correct
17 Correct 835 ms 5476 KB Output is correct
18 Correct 727 ms 5476 KB Output is correct
19 Correct 1308 ms 8248 KB Output is correct
20 Correct 3226 ms 5080 KB Output is correct
21 Correct 317 ms 1252 KB Output is correct
22 Correct 3698 ms 6268 KB Output is correct
23 Correct 1028 ms 10096 KB Output is correct
24 Correct 1208 ms 5740 KB Output is correct
25 Correct 2066 ms 10096 KB Output is correct
26 Correct 1828 ms 10096 KB Output is correct
27 Correct 1606 ms 10096 KB Output is correct
28 Correct 623 ms 32932 KB Output is correct
29 Correct 2119 ms 32536 KB Output is correct
30 Correct 5577 ms 28576 KB Output is correct
31 Correct 5045 ms 21712 KB Output is correct
32 Correct 414 ms 1384 KB Output is correct
33 Correct 638 ms 1912 KB Output is correct
34 Correct 1276 ms 32536 KB Output is correct
35 Correct 1512 ms 16696 KB Output is correct
36 Correct 2745 ms 32536 KB Output is correct
37 Correct 2233 ms 32536 KB Output is correct
38 Correct 2142 ms 32536 KB Output is correct
39 Correct 755 ms 70684 KB Output is correct
40 Correct 3310 ms 69628 KB Output is correct
41 Correct 7901 ms 60124 KB Output is correct
42 Correct 7104 ms 45472 KB Output is correct
43 Correct 1678 ms 69628 KB Output is correct
44 Correct 540 ms 1516 KB Output is correct
45 Correct 1876 ms 25012 KB Output is correct
46 Correct 3512 ms 69628 KB Output is correct
47 Correct 3585 ms 69628 KB Output is correct
48 Correct 3335 ms 69628 KB Output is correct
49 Correct 0 ms 1252 KB Output is correct