Submission #13388

#	Time	Username	Problem	Language	Result	Execution time	Memory
13388		baneling100	Game (IOI13_game)	C++98	100 / 100	6784 ms	76452 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20