oj.uz

Submission #1101359

# Submission time Handle Problem Language Result Execution time Memory
1101359 2024-10-16T07:08:35 Z alexander707070 Game (IOI13_game) C++14
63 / 100
 1260 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
 
#define MAXN 25007
using namespace std;
 
const int maxs=1e9;
 
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;
}

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 check(int v){
        if(tree[v].l==0){
            addnode(); tree[v].l=num;
        }
        if(tree[v].r==0){
            addnode(); tree[v].r=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;
            check(v);

            if(pos<=tt)update(tree[v].l,l,tt,pos,val);
            else update(tree[v].r,tt+1,r,pos,val);

            tree[v].val=gcd2(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 gcd2( 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 check(int v){
        if(tree[v].l==0){
            addnode(); tree[v].l=num;
        }
        if(tree[v].r==0){
            addnode(); tree[v].r=num;
        }
    }
 
    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;
            check(v);
 
            if(posx<=tt)update(tree[v].l,l,tt,posx,posy,val);
            else 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 gcd2( 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 2 ms 2384 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2652 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 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 1 ms 2384 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 547 ms 54088 KB Output is correct
5 Correct 450 ms 52552 KB Output is correct
6 Correct 525 ms 49736 KB Output is correct
7 Correct 549 ms 49392 KB Output is correct
8 Correct 397 ms 31048 KB Output is correct
9 Correct 546 ms 49740 KB Output is correct
10 Correct 542 ms 49228 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 3 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2396 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 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 885 ms 20296 KB Output is correct
13 Correct 1104 ms 10728 KB Output is correct
14 Correct 413 ms 3172 KB Output is correct
15 Correct 1235 ms 15320 KB Output is correct
16 Correct 415 ms 25124 KB Output is correct
17 Correct 873 ms 18400 KB Output is correct
18 Correct 1260 ms 25416 KB Output is correct
19 Correct 1065 ms 26208 KB Output is correct
20 Correct 1043 ms 25672 KB Output is correct
21 Correct 1 ms 2384 KB Output is correct

Subtask #4
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 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 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 538 ms 54024 KB Output is correct
13 Correct 434 ms 52760 KB Output is correct
14 Correct 542 ms 49736 KB Output is correct
15 Correct 561 ms 49480 KB Output is correct
16 Correct 397 ms 31048 KB Output is correct
17 Correct 555 ms 49736 KB Output is correct
18 Correct 537 ms 49224 KB Output is correct
19 Correct 872 ms 20488 KB Output is correct
20 Correct 1072 ms 10748 KB Output is correct
21 Correct 406 ms 3092 KB Output is correct
22 Correct 1210 ms 15432 KB Output is correct
23 Correct 402 ms 25160 KB Output is correct
24 Correct 828 ms 18276 KB Output is correct
25 Correct 1260 ms 25400 KB Output is correct
26 Correct 1100 ms 26156 KB Output is correct
27 Correct 1124 ms 25672 KB Output is correct
28 Runtime error 762 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 3 ms 2808 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 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 604 ms 54088 KB Output is correct
13 Correct 427 ms 52552 KB Output is correct
14 Correct 567 ms 49724 KB Output is correct
15 Correct 568 ms 49564 KB Output is correct
16 Correct 417 ms 30832 KB Output is correct
17 Correct 579 ms 49868 KB Output is correct
18 Correct 550 ms 49328 KB Output is correct
19 Correct 886 ms 20460 KB Output is correct
20 Correct 1076 ms 10824 KB Output is correct
21 Correct 449 ms 3144 KB Output is correct
22 Correct 1219 ms 15308 KB Output is correct
23 Correct 417 ms 25160 KB Output is correct
24 Correct 857 ms 18316 KB Output is correct
25 Correct 1216 ms 25416 KB Output is correct
26 Correct 1077 ms 26244 KB Output is correct
27 Correct 1098 ms 25624 KB Output is correct
28 Runtime error 775 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -