oj.uz

Submission #16833

# Submission time Handle Problem Language Result Execution time Memory
16833 2015-10-07T05:28:57 Z comet Game (IOI13_game) C++
0 / 100
 1 ms 1756 KB 
#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);
    }
    ~SegTree(){
        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,*p;
    Node2(int s_,int e_):s(s_),e(e_){
        tree=new SegTree(0,R-1);
        LL=RR=p=NULL;
    }
    ~Node2(){
        if(LL!=NULL)delete LL;
        if(RR!=NULL)delete RR;
        delete tree;
    }
    void update(int x,int y,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;
            }
            Node2* t=new Node2(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->tree=tree;
            t->update(x,y,c);
            return;
        }
        if(s==e){
            tree->update(y,c);
            return;
        }
        if(x<=mid){
            if(LL==NULL){
                LL=new Node2(x,x);
                LL->p=this;
            }
            LL->update(x,y,c);
        }
        else{
            if(RR==NULL){
                RR=new Node2(x,x);
                RR->p=this;
            }
            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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Incorrect 1 ms 1756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Incorrect 0 ms 1756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Incorrect 0 ms 1756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Incorrect 0 ms 1756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Incorrect 0 ms 1756 KB Output isn't correct
3 Halted 0 ms 0 KB -