oj.uz

Submission #13375

# Submission time Handle Problem Language Result Execution time Memory
13375 2015-02-14T05:31:43 Z dohyun0324 Game (IOI13_game) C++
63 / 100
 3330 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 rx,ry;
    data *l,*r;
    data(int s,int e):rx(s),ry(e){
        l=r=NULL;
    }
    void update3()
    {
        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->rx=rx; l->ry=mid; l->update3();
        }
        else
        {
            if(r==NULL) r=new data(mid+1,ry);
            r->rx=mid+1; r->ry=ry; r->update3();
        }
        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 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)
        {
            r->rx=mid+1; r->ry=ry;
            return r->query();
        }
        else if(r==NULL)
        {
            l->rx=rx; l->ry=mid;
            return l->query();
        }
        l->rx=rx; l->ry=mid;
        r->rx=mid+1; r->ry=ry;
        return gcd2(l->query(),r->query());
    }
    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);
};
data start=data(1,n);
void init(int R, int C){
    n=R+1, m=C+1;
    start=data(1,n);
}
void update(int P, int Q, ll K){
    x1=P+1; y1=Q+1; k=K;
    start.update3();
}
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();
}

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 1 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 745 ms 9836 KB Output is correct
5 Correct 511 ms 9836 KB Output is correct
6 Correct 807 ms 10100 KB Output is correct
7 Correct 840 ms 10100 KB Output is correct
8 Correct 539 ms 6140 KB Output is correct
9 Correct 861 ms 10100 KB Output is correct
10 Correct 733 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 1 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 1 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 1204 ms 12608 KB Output is correct
13 Correct 2931 ms 6404 KB Output is correct
14 Correct 357 ms 1388 KB Output is correct
15 Correct 3330 ms 8912 KB Output is correct
16 Correct 1109 ms 18416 KB Output is correct
17 Correct 1314 ms 11024 KB Output is correct
18 Correct 2095 ms 18416 KB Output is correct
19 Correct 1805 ms 18416 KB Output is correct
20 Correct 1655 ms 18416 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 1 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 703 ms 9836 KB Output is correct
13 Correct 511 ms 9836 KB Output is correct
14 Correct 797 ms 10100 KB Output is correct
15 Correct 881 ms 10100 KB Output is correct
16 Correct 547 ms 6140 KB Output is correct
17 Correct 840 ms 10100 KB Output is correct
18 Correct 687 ms 10100 KB Output is correct
19 Correct 1200 ms 12608 KB Output is correct
20 Correct 2940 ms 6404 KB Output is correct
21 Correct 351 ms 1388 KB Output is correct
22 Correct 3318 ms 8912 KB Output is correct
23 Correct 1085 ms 18416 KB Output is correct
24 Correct 1265 ms 11024 KB Output is correct
25 Correct 2080 ms 18416 KB Output is correct
26 Correct 1816 ms 18416 KB Output is correct
27 Correct 1650 ms 18416 KB Output is correct
28 Correct 1088 ms 251396 KB Output is correct
29 Memory limit exceeded 2256 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 723 ms 9836 KB Output is correct
13 Correct 537 ms 9836 KB Output is correct
14 Correct 763 ms 10100 KB Output is correct
15 Correct 818 ms 10100 KB Output is correct
16 Correct 555 ms 6140 KB Output is correct
17 Correct 830 ms 10100 KB Output is correct
18 Correct 696 ms 10100 KB Output is correct
19 Correct 1263 ms 12608 KB Output is correct
20 Correct 2901 ms 6404 KB Output is correct
21 Correct 383 ms 1388 KB Output is correct
22 Correct 3316 ms 8912 KB Output is correct
23 Correct 1092 ms 18416 KB Output is correct
24 Correct 1326 ms 11024 KB Output is correct
25 Correct 2056 ms 18416 KB Output is correct
26 Correct 1822 ms 18416 KB Output is correct
27 Correct 1633 ms 18416 KB Output is correct
28 Correct 1069 ms 251396 KB Output is correct
29 Memory limit exceeded 2238 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -