oj.uz

Submission #1101756

# Submission time Handle Problem Language Result Execution time Memory
1101756 2024-10-16T18:10:05 Z alexander707070 Game (IOI13_game) C++14
0 / 100
 3 ms 4548 KB 
#include<bits/stdc++.h>
#include "game.h"
 
#define MAXN 25007
using namespace std;
 
const int maxs=1e9;

unordered_map<int,int> mp;

struct node{
    int l,r,dest;

    long long val;
};

int num;
node tree[400*MAXN];

struct ST{

    int root;

    void init(){
        num++;
        root=num;
    }

    void addnode(){
        num++;
    }

    void down(int v,int l,int r,int pos,long long val){
        if(l==r){
            tree[v].val=__gcd(tree[v].val,val);
            return;
        }
        
        if(tree[v].dest==0){
            tree[v].dest=pos;
            tree[v].val=val;
            return;
        }

        int tt=(l+r)/2;
        addnode();

        if(tree[v].dest<=tt)tree[v].l=num;
        else tree[v].r=num;

        tree[num].dest=tree[v].dest;
        tree[num].val=tree[v].val;

        tree[v].dest=0;

        if(pos<=tt){
            if(tree[v].l==0){
                addnode(); tree[v].l=num;
            }
            down(tree[v].l,l,tt,pos,val);
        }else{
            if(tree[v].r==0){
                addnode(); tree[v].r=num;
            }
            down(tree[v].r,tt+1,r,pos,val);
        }

        tree[v].val=__gcd(tree[tree[v].l].val,tree[tree[v].r].val);
    }

    void update(int v,int l,int r,int pos,long long val){
        if(l==r){
            tree[v].val=val;
        }else{
            int tt=(l+r)/2;

            if(tree[v].dest!=0){
                down(v,l,r,pos,val);
                return;
            }

            if(pos<=tt){
                if(tree[v].l==0){
                    addnode(); 
                    tree[v].l=num;

                    tree[num].dest=pos;
                    tree[num].val=val;
                }else{
                    update(tree[v].l,l,tt,pos,val);
                }
            }else{
                if(tree[v].r==0){
                    addnode(); 
                    tree[v].r=num;

                    tree[num].dest=pos;
                    tree[num].val=val;
                }else{
                    update(tree[v].r,tt+1,r,pos,val);
                }
            }

            tree[v].val=__gcd(tree[tree[v].l].val,tree[tree[v].r].val);
        }
    }

    long long getgcd(int v,int l,int r,int ll,int rr){
        if(v==0 or ll>rr)return 0;
        if(tree[v].dest!=0)return tree[v].val;

        if(l==ll and r==rr){
            return tree[v].val;
        }else{
            int tt=(l+r)/2;
            return __gcd( getgcd(tree[v].l,l,tt,ll,min(tt,rr)) , getgcd(tree[v].r,tt+1,r,max(tt+1,ll),rr) );
        }
    }

    void upd(int pos,long long val){
        update(root,1,maxs,pos,val);
    }

    long long query(int l,int r){
        return getgcd(root,1,maxs,l,r);
    }
};

int last,currid;
ST col[MAXN];
 
struct ST2D{
 
    struct node{
        int l,r;
        ST t;
    };
 
    node tree[35*MAXN];
    int num;
 
    void init(){
        tree[1].t.init();
        num=1;
    }
 
    void addnode(){
        num++;
        tree[num].t.init();
    }
 
    void update(int v,int l,int r,int posx,int posy,long long val){
        if(l==r){
            tree[v].t.upd(posy,val);
        }else{
            int tt=(l+r)/2;

            if(posx<=tt){
                if(tree[v].l==0){
                    addnode(); tree[v].l=num;
                }
                update(tree[v].l,l,tt,posx,posy,val);
            }else{
                if(tree[v].r==0){
                    addnode(); tree[v].r=num;
                }
                update(tree[v].r,tt+1,r,posx,posy,val);
            }

            long long newval = col[currid].query(l,r);
            tree[v].t.upd(posy,newval);
        }
    }
 
    long long getgcd(int v,int l,int r,int lx,int rx,int ly,int ry){
        if(v==0 or lx>rx)return 0;
 
        if(l==lx and r==rx){
            return tree[v].t.query(ly,ry);
        }else{
            int tt=(l+r)/2;
            return __gcd( getgcd(tree[v].l,l,tt,lx,min(tt,rx),ly,ry) , getgcd(tree[v].r,tt+1,r,max(tt+1,lx),rx,ly,ry) );
        }
    }
 
    void upd(int x,int y,long long val){
        update(1,1,maxs,x,y,val);
    }
 
    long long query(int a,int b,int c,int d){
        return getgcd(1,1,maxs,a,c,b,d);
    }
}seg;
 
void init(int R, int C) {
    seg.init();
}
 
void update(int P, int Q, long long K) {
    P++; Q++;

    if(mp[Q]==0){
        last++; mp[Q]=last;
        col[last].init();
    }

    currid=mp[Q];
    col[currid].upd(P,K);

    seg.upd(P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
    P++; Q++; U++; V++;
    return seg.query(P,Q,U,V);
}
 
/*int main(){
 
    init(10,10);
 
    update(0,0,20);
    update(0,2,15);
    update(1,1,12);
 
    cout<<calculate(0,0,0,2)<<"\n";
    cout<<calculate(0,0,1,1)<<"\n";
    
    update(0,1,6);
    update(1,1,14);
 
    cout<<calculate(0,0,0,2)<<"\n";
    cout<<calculate(0,0,1,1)<<"\n";
 
	return 0;
}*/

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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