Submission #16832

#	Time	Username	Problem	Language	Result	Execution time	Memory
16832		comet	Game (IOI13_game)	C++98	100 / 100	7724 ms	99716 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll gcd2(ll,ll);
int R,C;
struct Node{
    int s,e;
    ll GCD;
    Node *LL,*RR,*p;
    Node(int s_,int e_):s(s_),e(e_){
        GCD=0;
        LL=RR=p=NULL;
    }
    ~Node(){
        if(LL!=NULL)delete LL;
        if(RR!=NULL)delete RR;
    }
    void up(){
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->GCD;
        if(RR!=NULL)z1=RR->GCD;
        GCD=gcd2(z0,z1);
    }
    void update(int x,ll c){
        int mid=(s+e)/2;
        if(x<s||x>e){
            int pL=p->s,pR=p->e,L,R;
            L=pL,R=pR;
            while(L<=s&&e<=R){
                pL=L,pR=R;
                mid=(L+R)/2;
                if(x<=mid)R=mid;
                else L=mid+1;
            }
            Node* t=new Node(pL,pR);
            mid=(p->s+p->e)/2;
            if(pR<=mid)p->LL=t;
            else p->RR=t;
            mid=(pL+pR)/2;
            if(x<=mid)t->RR=this;
            else t->LL=this;
            t->p=p;
            p=t;
            t->update(x,c);
            return;
        }
        if(s==e){
            GCD=c;
            return;
        }
        if(x<=mid){
            if(LL==NULL){
                LL=new Node(x,x);
                LL->p=this;
            }
            LL->update(x,c);
        }
        else{
            if(RR==NULL){
                RR=new Node(x,x);
                RR->p=this;
            }
            RR->update(x,c);
        }
        up();
    }
    ll query(int L,int R){
        if(e<L||s>R)return 0;
        if(L<=s&&e<=R)return GCD;
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->query(L,R);
        if(RR!=NULL)z1=RR->query(L,R);
        return gcd2(z0,z1);
    }
};

struct SegTree{
    Node *root;
    SegTree(int s=0,int e=0){
        root=new Node(s,e);
    }
    void finish(){
        delete root;
    }
    void update(int x,ll c){
        root->update(x,c);
    }
    ll query(int s,int e){
        return root->query(s,e);
    }
};

struct Node2{
    int s,e;
    SegTree tree;
    Node2 *LL,*RR;
    Node2(int s_,int e_):s(s_),e(e_){
        tree=SegTree(0,R-1);
        LL=RR=NULL;
    }
    ~Node2(){
        if(LL!=NULL)delete LL;
        if(RR!=NULL)delete RR;
    }
    void update(int x,int y,ll c){
        int mid=(s+e)/2;
        if(s==e){
            tree.update(y,c);
            return;
        }
        if(x<=mid){
            if(LL==NULL)LL=new Node2(s,mid);
            LL->update(x,y,c);
        }
        else{
            if(RR==NULL)RR=new Node2(mid+1,e);
            RR->update(x,y,c);
        }
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->tree.query(y,y);
        if(RR!=NULL)z1=RR->tree.query(y,y);
        tree.update(y,gcd2(z0,z1));
    }
    ll query(int lo,int hi,int L,int R){
        if(e<lo||s>hi)return 0;
        if(lo<=s&&e<=hi)return tree.query(L,R);
        ll z0=0,z1=0;
        if(LL!=NULL)z0=LL->query(lo,hi,L,R);
        if(RR!=NULL)z1=RR->query(lo,hi,L,R);
        return gcd2(z0,z1);
    }
};

struct SegTree2{
    Node2 *root;
    SegTree2(int s=0,int e=0){
        root=new Node2(s,e);
    }
    void finish(){
        delete root;
    }
    void update(int x,int y,ll c){
        root->update(x,y,c);
    }
    ll query(int lo,int hi,int L,int R){
        return root->query(lo,hi,L,R);
    }
}game;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void init(int R_, int C_) {
    R=R_,C=C_;
    game=SegTree2(0,C-1);
}

void update(int P, int Q, long long K) {
    game.update(Q,P,K);
}

long long calculate(int P, int Q, int U, int V) {
    return game.query(Q,V,P,U);
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20