oj.uz

Submission #1101771

# Submission time Handle Problem Language Result Execution time Memory
1101771 2024-10-16T18:24:35 Z alexander707070 Game (IOI13_game) C++14
100 / 100
 2575 ms 89652 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){
            if(tree[v].dest>=ll and tree[v].dest<=rr)return tree[v].val;
            else return 0;
        }

        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
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 2384 KB Output is correct
5 Correct 1 ms 2552 KB Output is correct
6 Correct 2 ms 4540 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 4604 KB Output is correct
11 Correct 1 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 2 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 434 ms 25380 KB Output is correct
5 Correct 354 ms 25456 KB Output is correct
6 Correct 467 ms 22188 KB Output is correct
7 Correct 460 ms 21332 KB Output is correct
8 Correct 322 ms 12872 KB Output is correct
9 Correct 451 ms 21108 KB Output is correct
10 Correct 422 ms 21068 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 2560 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4432 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 4604 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 4556 KB Output is correct
10 Correct 2 ms 4432 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 783 ms 14716 KB Output is correct
13 Correct 1041 ms 9288 KB Output is correct
14 Correct 398 ms 4936 KB Output is correct
15 Correct 1228 ms 13456 KB Output is correct
16 Correct 379 ms 13616 KB Output is correct
17 Correct 745 ms 11936 KB Output is correct
18 Correct 1182 ms 13816 KB Output is correct
19 Correct 1002 ms 13896 KB Output is correct
20 Correct 1010 ms 13320 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 4432 KB Output is correct
3 Correct 2 ms 4544 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 2 ms 4432 KB Output is correct
12 Correct 443 ms 25340 KB Output is correct
13 Correct 349 ms 25544 KB Output is correct
14 Correct 446 ms 22344 KB Output is correct
15 Correct 506 ms 21244 KB Output is correct
16 Correct 336 ms 12860 KB Output is correct
17 Correct 442 ms 21064 KB Output is correct
18 Correct 403 ms 20828 KB Output is correct
19 Correct 825 ms 14608 KB Output is correct
20 Correct 1118 ms 9528 KB Output is correct
21 Correct 436 ms 4936 KB Output is correct
22 Correct 1200 ms 13520 KB Output is correct
23 Correct 359 ms 13384 KB Output is correct
24 Correct 760 ms 11984 KB Output is correct
25 Correct 1096 ms 13684 KB Output is correct
26 Correct 1060 ms 13864 KB Output is correct
27 Correct 963 ms 13448 KB Output is correct
28 Correct 309 ms 26164 KB Output is correct
29 Correct 728 ms 25160 KB Output is correct
30 Correct 2146 ms 25988 KB Output is correct
31 Correct 1978 ms 46472 KB Output is correct
32 Correct 318 ms 4936 KB Output is correct
33 Correct 427 ms 7108 KB Output is correct
34 Correct 117 ms 22192 KB Output is correct
35 Correct 533 ms 14388 KB Output is correct
36 Correct 861 ms 22292 KB Output is correct
37 Correct 725 ms 22564 KB Output is correct
38 Correct 773 ms 21920 KB Output is correct
39 Correct 700 ms 18468 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 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 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 2 ms 4496 KB Output is correct
12 Correct 416 ms 25372 KB Output is correct
13 Correct 332 ms 25496 KB Output is correct
14 Correct 422 ms 22392 KB Output is correct
15 Correct 456 ms 21252 KB Output is correct
16 Correct 315 ms 12684 KB Output is correct
17 Correct 439 ms 21064 KB Output is correct
18 Correct 399 ms 21008 KB Output is correct
19 Correct 759 ms 14700 KB Output is correct
20 Correct 1142 ms 9288 KB Output is correct
21 Correct 376 ms 4936 KB Output is correct
22 Correct 1214 ms 13600 KB Output is correct
23 Correct 354 ms 13384 KB Output is correct
24 Correct 734 ms 12116 KB Output is correct
25 Correct 1065 ms 13700 KB Output is correct
26 Correct 1024 ms 13896 KB Output is correct
27 Correct 929 ms 13364 KB Output is correct
28 Correct 259 ms 26184 KB Output is correct
29 Correct 746 ms 25160 KB Output is correct
30 Correct 2110 ms 26008 KB Output is correct
31 Correct 1979 ms 46624 KB Output is correct
32 Correct 378 ms 4936 KB Output is correct
33 Correct 492 ms 6984 KB Output is correct
34 Correct 118 ms 22088 KB Output is correct
35 Correct 580 ms 14296 KB Output is correct
36 Correct 947 ms 22296 KB Output is correct
37 Correct 733 ms 22576 KB Output is correct
38 Correct 735 ms 22088 KB Output is correct
39 Correct 380 ms 55204 KB Output is correct
40 Correct 986 ms 48224 KB Output is correct
41 Correct 2575 ms 49252 KB Output is correct
42 Correct 2508 ms 89652 KB Output is correct
43 Correct 191 ms 47356 KB Output is correct
44 Correct 509 ms 4936 KB Output is correct
45 Correct 654 ms 18560 KB Output is correct
46 Correct 1109 ms 47684 KB Output is correct
47 Correct 1238 ms 46460 KB Output is correct
48 Correct 1118 ms 47236 KB Output is correct
49 Correct 1 ms 2384 KB Output is correct