oj.uz

Submission #1101360

# Submission time Handle Problem Language Result Execution time Memory
1101360 2024-10-16T07:13:11 Z alexander707070 Game (IOI13_game) C++14
80 / 100
 2314 ms 256000 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;
    long long val;
};

int num;
node tree[500*MAXN];

struct ST{

    int root;

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

    void addnode(){
        num++;
    }

    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(pos<=tt){
                if(tree[v].l==0){
                    addnode(); tree[v].l=num;
                }
                update(tree[v].l,l,tt,pos,val);
            }else{
                if(tree[v].r==0){
                    addnode(); tree[v].r=num;
                }
                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(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 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 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 2640 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 2384 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 2552 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 470 ms 35516 KB Output is correct
5 Correct 385 ms 34476 KB Output is correct
6 Correct 493 ms 31564 KB Output is correct
7 Correct 490 ms 31152 KB Output is correct
8 Correct 370 ms 20552 KB Output is correct
9 Correct 493 ms 31316 KB Output is correct
10 Correct 478 ms 31048 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 2640 KB Output is correct
3 Correct 2 ms 2640 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 2640 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 2384 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 775 ms 14996 KB Output is correct
13 Correct 1010 ms 8008 KB Output is correct
14 Correct 359 ms 3156 KB Output is correct
15 Correct 1142 ms 10656 KB Output is correct
16 Correct 350 ms 16500 KB Output is correct
17 Correct 723 ms 12292 KB Output is correct
18 Correct 1078 ms 16816 KB Output is correct
19 Correct 1014 ms 17992 KB Output is correct
20 Correct 939 ms 16464 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 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2640 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 4552 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 2 ms 4432 KB Output is correct
12 Correct 459 ms 35536 KB Output is correct
13 Correct 379 ms 34632 KB Output is correct
14 Correct 487 ms 31560 KB Output is correct
15 Correct 507 ms 31316 KB Output is correct
16 Correct 360 ms 20672 KB Output is correct
17 Correct 487 ms 31304 KB Output is correct
18 Correct 467 ms 30840 KB Output is correct
19 Correct 813 ms 15052 KB Output is correct
20 Correct 1074 ms 8080 KB Output is correct
21 Correct 358 ms 3144 KB Output is correct
22 Correct 1113 ms 10836 KB Output is correct
23 Correct 352 ms 16468 KB Output is correct
24 Correct 754 ms 12444 KB Output is correct
25 Correct 1038 ms 16696 KB Output is correct
26 Correct 1051 ms 17996 KB Output is correct
27 Correct 945 ms 16200 KB Output is correct
28 Correct 452 ms 138292 KB Output is correct
29 Correct 989 ms 158284 KB Output is correct
30 Correct 2247 ms 116420 KB Output is correct
31 Correct 2175 ms 91672 KB Output is correct
32 Correct 319 ms 12368 KB Output is correct
33 Correct 435 ms 13644 KB Output is correct
34 Correct 298 ms 151904 KB Output is correct
35 Correct 771 ms 85772 KB Output is correct
36 Correct 1247 ms 156004 KB Output is correct
37 Correct 1085 ms 156360 KB Output is correct
38 Correct 1028 ms 155736 KB Output is correct
39 Correct 898 ms 123192 KB Output is correct
40 Correct 1 ms 2388 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 2 ms 2524 KB Output is correct
3 Correct 2 ms 2640 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 2640 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 2384 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 511 ms 35652 KB Output is correct
13 Correct 364 ms 34488 KB Output is correct
14 Correct 497 ms 31612 KB Output is correct
15 Correct 520 ms 29220 KB Output is correct
16 Correct 372 ms 20552 KB Output is correct
17 Correct 514 ms 31388 KB Output is correct
18 Correct 493 ms 31048 KB Output is correct
19 Correct 854 ms 15080 KB Output is correct
20 Correct 1048 ms 8008 KB Output is correct
21 Correct 366 ms 3152 KB Output is correct
22 Correct 1174 ms 10824 KB Output is correct
23 Correct 380 ms 16384 KB Output is correct
24 Correct 797 ms 12436 KB Output is correct
25 Correct 1063 ms 16804 KB Output is correct
26 Correct 979 ms 17992 KB Output is correct
27 Correct 949 ms 16200 KB Output is correct
28 Correct 433 ms 138312 KB Output is correct
29 Correct 1061 ms 158092 KB Output is correct
30 Correct 2314 ms 116404 KB Output is correct
31 Correct 2286 ms 88292 KB Output is correct
32 Correct 340 ms 12276 KB Output is correct
33 Correct 442 ms 13640 KB Output is correct
34 Correct 310 ms 151888 KB Output is correct
35 Correct 840 ms 85836 KB Output is correct
36 Correct 1523 ms 155980 KB Output is correct
37 Correct 1267 ms 156360 KB Output is correct
38 Correct 1140 ms 155724 KB Output is correct
39 Runtime error 784 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -