oj.uz

Submission #13388

# Submission time Handle Problem Language Result Execution time Memory
13388 2015-02-15T17:04:39 Z baneling100 Game (IOI13_game) C++
100 / 100
 6784 ms 76452 KB 
#include "game.h"
#include <stdio.h>

struct Xnode {
    Xnode(int l_, int r_) {left=right=NULL, l=l_, r=r_, info=NULL;}
    Xnode *left, *right;
    int l, r;
    long long info;
};
struct Ynode {
    Ynode() {left=right=NULL, Xroot=NULL;}
    Ynode *left, *right;
    Xnode *Xroot;
} *Yroot;
int R, C, P, Q, U, V;
long long K;

long long gcd2(long long X, long long Y) {

    long long tmp;

    if(!X) {
        tmp=X;
        X=Y;
        Y=tmp;
    }
    while(X!=Y && Y!=0) {
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}

void init(int R_, int C_) {

    for(R=1 ; R<R_ ; R<<=1);
    for(C=1 ; C<C_ ; C<<=1);
    Yroot=new Ynode();
}

long long Xcalculate(Xnode *now) {

    long long value=0;

    if(Q<=now->l && now->r<=V) return now->info;
    else {
        if(now->left!=NULL && Q<=now->left->r && now->left->l<=V) value=Xcalculate(now->left);
        if(now->right!=NULL && Q<=now->right->r && now->right->l<=V) value=gcd2(value,Xcalculate(now->right));
        return value;
    }
}

long long Ycalculate(int l, int r, Ynode *now) {

    int m=(l+r)>>1;
    long long value=0;

    if(P<=l && r<=U) {
        if(now->Xroot!=NULL) value=Xcalculate(now->Xroot);
        return value;
    }
    else {
        if(P<=m && now->left!=NULL) value=Ycalculate(l,m,now->left);
        if(m+1<=U && now->right!=NULL) value=gcd2(value,Ycalculate(m+1,r,now->right));
        return value;
    }
}

void Xupdate(Xnode *now) {

    int m=(now->l+now->r)>>1, x, y;
    Xnode *temp;

    if(now->l==Q && Q==now->r) now->info=K;
    else {
        if(Q<=m) {
            if(now->left==NULL) now->left=new Xnode(Q,Q);
            if(Q<now->left->l || now->left->r<Q) {
                temp=now->left;
                now->left=new Xnode(now->l,m);
                if(Q<temp->l) now->left->right=temp;
                else now->left->left=temp;
                while(1) {
                    x=(now->left->r-now->left->l+1)>>1;
                    y=(now->left->l+now->left->r)>>1;
                    if(!(Q&x) && !(temp->l&x)) now->left->r=y;
                    else if(Q&x && temp->l&x) now->left->l=y+1;
                    else break;
                }
            }
            Xupdate(now->left);
        }
        else {
            if(now->right==NULL) now->right=new Xnode(Q,Q);
            if(Q<now->right->l || now->right->r<Q) {
                temp=now->right;
                now->right=new Xnode(m+1,now->r);
                if(Q<temp->l) now->right->right=temp;
                else now->right->left=temp;
                while(1) {
                    x=(now->right->r-now->right->l+1)>>1;
                    y=(now->right->l+now->right->r)>>1;
                    if(!(Q&x) && !(temp->l&x)) now->right->r=y;
                    else if(Q&x && temp->l&x) now->right->l=y+1;
                    else break;
                }
            }
            Xupdate(now->right);
        }
        if(now->right==NULL) now->info=now->left->info;
        else if(now->left==NULL) now->info=now->right->info;
        else now->info=gcd2(now->left->info,now->right->info);
    }
}

void Yupdate(int l, int r, Ynode *now) {

    int m=(l+r)>>1;

    if(l<r) {
        if(P<=m) {
            if(now->left==NULL) now->left=new Ynode();
            Yupdate(l,m,now->left);
        }
        if(m+1<=P) {
            if(now->right==NULL) now->right=new Ynode();
            Yupdate(m+1,r,now->right);
        }
        if(now->right==NULL) K=Xcalculate(now->left->Xroot);
        else if(now->left==NULL) K=Xcalculate(now->right->Xroot);
        else K=gcd2(Xcalculate(now->left->Xroot),Xcalculate(now->right->Xroot));
    }
    if(now->Xroot==NULL) now->Xroot=new Xnode(0,C-1);
    Xupdate(now->Xroot);
}

void update(int P_, int Q_, long long K_) {

    P=P_, Q=Q_, K=K_, V=Q;
    Yupdate(0,R-1,Yroot);
}

long long calculate(int P_, int Q_, int U_, int V_) {

    P=P_, Q=Q_, U=U_, V=V_;
    return Ycalculate(0,R-1,Yroot);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 0 ms 1212 KB Output is correct
3 Correct 0 ms 1212 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 0 ms 1212 KB Output is correct
7 Correct 0 ms 1212 KB Output is correct
8 Correct 0 ms 1212 KB Output is correct
9 Correct 0 ms 1212 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 0 ms 1212 KB Output is correct
12 Correct 0 ms 1212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 0 ms 1212 KB Output is correct
3 Correct 0 ms 1212 KB Output is correct
4 Correct 662 ms 5700 KB Output is correct
5 Correct 382 ms 5700 KB Output is correct
6 Correct 681 ms 5700 KB Output is correct
7 Correct 812 ms 5700 KB Output is correct
8 Correct 493 ms 3324 KB Output is correct
9 Correct 776 ms 5700 KB Output is correct
10 Correct 694 ms 5700 KB Output is correct
11 Correct 0 ms 1212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 1 ms 1212 KB Output is correct
3 Correct 0 ms 1212 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 0 ms 1212 KB Output is correct
7 Correct 0 ms 1212 KB Output is correct
8 Correct 0 ms 1212 KB Output is correct
9 Correct 0 ms 1212 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 0 ms 1212 KB Output is correct
12 Correct 1249 ms 8340 KB Output is correct
13 Correct 2964 ms 5172 KB Output is correct
14 Correct 304 ms 1212 KB Output is correct
15 Correct 3333 ms 6360 KB Output is correct
16 Correct 418 ms 10056 KB Output is correct
17 Correct 1125 ms 5832 KB Output is correct
18 Correct 1962 ms 10056 KB Output is correct
19 Correct 1652 ms 10056 KB Output is correct
20 Correct 1515 ms 10056 KB Output is correct
21 Correct 0 ms 1212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 0 ms 1212 KB Output is correct
3 Correct 1 ms 1212 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 0 ms 1212 KB Output is correct
7 Correct 0 ms 1212 KB Output is correct
8 Correct 0 ms 1212 KB Output is correct
9 Correct 0 ms 1212 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 0 ms 1212 KB Output is correct
12 Correct 627 ms 5700 KB Output is correct
13 Correct 405 ms 5700 KB Output is correct
14 Correct 698 ms 5700 KB Output is correct
15 Correct 812 ms 5700 KB Output is correct
16 Correct 486 ms 3324 KB Output is correct
17 Correct 800 ms 5700 KB Output is correct
18 Correct 660 ms 5700 KB Output is correct
19 Correct 1247 ms 8340 KB Output is correct
20 Correct 2977 ms 5172 KB Output is correct
21 Correct 303 ms 1212 KB Output is correct
22 Correct 3334 ms 6360 KB Output is correct
23 Correct 410 ms 10056 KB Output is correct
24 Correct 1085 ms 5832 KB Output is correct
25 Correct 1976 ms 10056 KB Output is correct
26 Correct 1652 ms 10056 KB Output is correct
27 Correct 1485 ms 10056 KB Output is correct
28 Correct 614 ms 35796 KB Output is correct
29 Correct 1961 ms 35268 KB Output is correct
30 Correct 4911 ms 30120 KB Output is correct
31 Correct 4438 ms 22860 KB Output is correct
32 Correct 424 ms 1344 KB Output is correct
33 Correct 635 ms 2004 KB Output is correct
34 Correct 906 ms 35268 KB Output is correct
35 Correct 1399 ms 18108 KB Output is correct
36 Correct 2545 ms 35268 KB Output is correct
37 Correct 2119 ms 35268 KB Output is correct
38 Correct 2012 ms 35268 KB Output is correct
39 Correct 1754 ms 27216 KB Output is correct
40 Correct 0 ms 1212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1212 KB Output is correct
2 Correct 1 ms 1212 KB Output is correct
3 Correct 0 ms 1212 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 0 ms 1212 KB Output is correct
6 Correct 0 ms 1212 KB Output is correct
7 Correct 0 ms 1212 KB Output is correct
8 Correct 0 ms 1212 KB Output is correct
9 Correct 0 ms 1212 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 0 ms 1212 KB Output is correct
12 Correct 654 ms 5700 KB Output is correct
13 Correct 384 ms 5700 KB Output is correct
14 Correct 711 ms 5700 KB Output is correct
15 Correct 804 ms 5700 KB Output is correct
16 Correct 492 ms 3324 KB Output is correct
17 Correct 813 ms 5700 KB Output is correct
18 Correct 768 ms 5700 KB Output is correct
19 Correct 1230 ms 8340 KB Output is correct
20 Correct 2978 ms 5172 KB Output is correct
21 Correct 311 ms 1212 KB Output is correct
22 Correct 3318 ms 6360 KB Output is correct
23 Correct 412 ms 10056 KB Output is correct
24 Correct 1089 ms 5832 KB Output is correct
25 Correct 1950 ms 10056 KB Output is correct
26 Correct 1620 ms 10056 KB Output is correct
27 Correct 1443 ms 10056 KB Output is correct
28 Correct 593 ms 35796 KB Output is correct
29 Correct 1923 ms 35268 KB Output is correct
30 Correct 4845 ms 30120 KB Output is correct
31 Correct 4503 ms 22860 KB Output is correct
32 Correct 409 ms 1344 KB Output is correct
33 Correct 632 ms 2004 KB Output is correct
34 Correct 900 ms 35268 KB Output is correct
35 Correct 1412 ms 18108 KB Output is correct
36 Correct 2540 ms 35268 KB Output is correct
37 Correct 2099 ms 35268 KB Output is correct
38 Correct 2007 ms 35268 KB Output is correct
39 Correct 765 ms 76452 KB Output is correct
40 Correct 3059 ms 75396 KB Output is correct
41 Correct 6784 ms 63252 KB Output is correct
42 Correct 6206 ms 47808 KB Output is correct
43 Correct 1448 ms 75396 KB Output is correct
44 Correct 548 ms 1476 KB Output is correct
45 Correct 1766 ms 27216 KB Output is correct
46 Correct 3283 ms 75528 KB Output is correct
47 Correct 3336 ms 75396 KB Output is correct
48 Correct 3107 ms 75396 KB Output is correct
49 Correct 0 ms 1212 KB Output is correct