oj.uz

Submission #13374

# Submission time Handle Problem Language Result Execution time Memory
13374 2015-02-14T04:58:11 Z dohyun0324 Game (IOI13_game) C++
63 / 100
 3317 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
{
    data *l,*r;
    data(){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();
            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(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
    {
        ll val;
        data2 *l,*r;
        data2(){}
        data2(ll v):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(0);
                l->update2(cx,mid);
            }
            else{
                if(r==NULL) r=new data2(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(0);
};
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 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 0 ms 1256 KB Output is correct
5 Correct 0 ms 1256 KB Output is correct
6 Correct 0 ms 1256 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 1256 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 731 ms 9836 KB Output is correct
5 Correct 516 ms 9836 KB Output is correct
6 Correct 762 ms 10100 KB Output is correct
7 Correct 878 ms 10100 KB Output is correct
8 Correct 541 ms 6140 KB Output is correct
9 Correct 840 ms 10100 KB Output is correct
10 Correct 700 ms 10100 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 1256 KB Output is correct
3 Correct 0 ms 1256 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 1256 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 1256 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct
12 Correct 1221 ms 12608 KB Output is correct
13 Correct 2896 ms 6404 KB Output is correct
14 Correct 358 ms 1388 KB Output is correct
15 Correct 3259 ms 8912 KB Output is correct
16 Correct 1057 ms 18284 KB Output is correct
17 Correct 1299 ms 11024 KB Output is correct
18 Correct 2060 ms 18284 KB Output is correct
19 Correct 1824 ms 18284 KB Output is correct
20 Correct 1666 ms 18284 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 1256 KB Output is correct
3 Correct 0 ms 1256 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 1256 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 1256 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 1 ms 1256 KB Output is correct
12 Correct 732 ms 9836 KB Output is correct
13 Correct 516 ms 9836 KB Output is correct
14 Correct 774 ms 10100 KB Output is correct
15 Correct 871 ms 10100 KB Output is correct
16 Correct 561 ms 6140 KB Output is correct
17 Correct 854 ms 10100 KB Output is correct
18 Correct 699 ms 10100 KB Output is correct
19 Correct 1202 ms 12608 KB Output is correct
20 Correct 2914 ms 6404 KB Output is correct
21 Correct 359 ms 1388 KB Output is correct
22 Correct 3317 ms 8912 KB Output is correct
23 Correct 1089 ms 18284 KB Output is correct
24 Correct 1299 ms 11024 KB Output is correct
25 Correct 2087 ms 18284 KB Output is correct
26 Correct 1794 ms 18284 KB Output is correct
27 Correct 1586 ms 18284 KB Output is correct
28 Correct 1087 ms 248624 KB Output is correct
29 Memory limit exceeded 2311 ms 256000 KB Memory limit exceeded
30 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 1256 KB Output is correct
3 Correct 0 ms 1256 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 1256 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 1256 KB Output is correct
10 Correct 0 ms 1256 KB Output is correct
11 Correct 0 ms 1256 KB Output is correct
12 Correct 716 ms 9836 KB Output is correct
13 Correct 521 ms 9836 KB Output is correct
14 Correct 778 ms 10100 KB Output is correct
15 Correct 853 ms 10100 KB Output is correct
16 Correct 579 ms 6140 KB Output is correct
17 Correct 850 ms 10100 KB Output is correct
18 Correct 687 ms 10100 KB Output is correct
19 Correct 1245 ms 12608 KB Output is correct
20 Correct 2900 ms 6404 KB Output is correct
21 Correct 349 ms 1388 KB Output is correct
22 Correct 3273 ms 8912 KB Output is correct
23 Correct 1064 ms 18284 KB Output is correct
24 Correct 1307 ms 11024 KB Output is correct
25 Correct 2072 ms 18284 KB Output is correct
26 Correct 1831 ms 18284 KB Output is correct
27 Correct 1608 ms 18284 KB Output is correct
28 Correct 1073 ms 248624 KB Output is correct
29 Memory limit exceeded 2291 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -