oj.uz

Submission #1101770

# Submission time Handle Problem Language Result Execution time Memory
1101770 2024-10-16T18:21:51 Z alexander707070 Game (IOI13_game) C++14
100 / 100
 2772 ms 105136 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=val;
            tree[v].dest=0;
            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;
            if(tree[v].dest!=0){
                addnode();
                if(tree[v].dest<=tt)tree[v].l=num;
                else tree[v].r=num;

                tree[num].val=tree[v].val;
                tree[num].dest=tree[v].dest;
                tree[v].dest=0;
            }
            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
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 441 ms 35852 KB Output is correct
5 Correct 354 ms 35584 KB Output is correct
6 Correct 436 ms 35144 KB Output is correct
7 Correct 475 ms 34940 KB Output is correct
8 Correct 314 ms 22844 KB Output is correct
9 Correct 499 ms 34888 KB Output is correct
10 Correct 447 ms 34632 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 4 ms 4432 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 2 ms 4548 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 835 ms 20940 KB Output is correct
13 Correct 994 ms 13292 KB Output is correct
14 Correct 423 ms 9544 KB Output is correct
15 Correct 1171 ms 17956 KB Output is correct
16 Correct 345 ms 19784 KB Output is correct
17 Correct 846 ms 20928 KB Output is correct
18 Correct 1147 ms 27420 KB Output is correct
19 Correct 1139 ms 27432 KB Output is correct
20 Correct 1018 ms 26992 KB Output is correct
21 Correct 1 ms 2384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 4548 KB Output is correct
3 Correct 2 ms 4600 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 438 ms 35912 KB Output is correct
13 Correct 337 ms 35584 KB Output is correct
14 Correct 443 ms 35144 KB Output is correct
15 Correct 473 ms 34888 KB Output is correct
16 Correct 310 ms 22856 KB Output is correct
17 Correct 468 ms 34932 KB Output is correct
18 Correct 452 ms 34632 KB Output is correct
19 Correct 750 ms 20808 KB Output is correct
20 Correct 977 ms 13192 KB Output is correct
21 Correct 368 ms 9728 KB Output is correct
22 Correct 1114 ms 17812 KB Output is correct
23 Correct 334 ms 19744 KB Output is correct
24 Correct 803 ms 21004 KB Output is correct
25 Correct 1241 ms 27240 KB Output is correct
26 Correct 1111 ms 27464 KB Output is correct
27 Correct 952 ms 26952 KB Output is correct
28 Correct 354 ms 46028 KB Output is correct
29 Correct 810 ms 43448 KB Output is correct
30 Correct 2231 ms 39048 KB Output is correct
31 Correct 2181 ms 57488 KB Output is correct
32 Correct 306 ms 14112 KB Output is correct
33 Correct 419 ms 16100 KB Output is correct
34 Correct 161 ms 37020 KB Output is correct
35 Correct 659 ms 34276 KB Output is correct
36 Correct 1118 ms 55512 KB Output is correct
37 Correct 931 ms 53576 KB Output is correct
38 Correct 888 ms 52988 KB Output is correct
39 Correct 816 ms 45128 KB Output is correct
40 Correct 1 ms 2384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2548 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 3 ms 4432 KB Output is correct
4 Correct 1 ms 2504 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 2 ms 4432 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 446 ms 35832 KB Output is correct
13 Correct 352 ms 35656 KB Output is correct
14 Correct 460 ms 35144 KB Output is correct
15 Correct 474 ms 34896 KB Output is correct
16 Correct 350 ms 22948 KB Output is correct
17 Correct 444 ms 34836 KB Output is correct
18 Correct 421 ms 34508 KB Output is correct
19 Correct 737 ms 20808 KB Output is correct
20 Correct 983 ms 13128 KB Output is correct
21 Correct 371 ms 9624 KB Output is correct
22 Correct 1099 ms 18024 KB Output is correct
23 Correct 331 ms 19708 KB Output is correct
24 Correct 807 ms 21236 KB Output is correct
25 Correct 1352 ms 27236 KB Output is correct
26 Correct 1140 ms 27468 KB Output is correct
27 Correct 983 ms 26992 KB Output is correct
28 Correct 301 ms 46216 KB Output is correct
29 Correct 810 ms 43428 KB Output is correct
30 Correct 2243 ms 38984 KB Output is correct
31 Correct 2175 ms 57568 KB Output is correct
32 Correct 302 ms 14152 KB Output is correct
33 Correct 412 ms 16084 KB Output is correct
34 Correct 176 ms 37192 KB Output is correct
35 Correct 690 ms 34380 KB Output is correct
36 Correct 1518 ms 55624 KB Output is correct
37 Correct 1000 ms 53576 KB Output is correct
38 Correct 1199 ms 53052 KB Output is correct
39 Correct 488 ms 86692 KB Output is correct
40 Correct 1195 ms 76200 KB Output is correct
41 Correct 2772 ms 70492 KB Output is correct
42 Correct 2579 ms 105136 KB Output is correct
43 Correct 244 ms 69052 KB Output is correct
44 Correct 402 ms 14524 KB Output is correct
45 Correct 798 ms 45204 KB Output is correct
46 Correct 1365 ms 95656 KB Output is correct
47 Correct 1442 ms 95692 KB Output is correct
48 Correct 1217 ms 95144 KB Output is correct
49 Correct 1 ms 2388 KB Output is correct