oj.uz

Submission #1101356

# Submission time Handle Problem Language Result Execution time Memory
1101356 2024-10-16T07:03:10 Z alexander707070 Game (IOI13_game) C++14
63 / 100
 1310 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 ST{
    struct node{
        int l,r;
        long long val;
    };

    vector<node> tree;
    int num;

    void init(){
        tree.push_back({0,0,0});
        tree.push_back({0,0,0});
        num=1;
    }

    void addnode(){
        num++; tree.push_back({0,0,0});
    }
    
    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(1,1,maxs,pos,val);
    }

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

int last,currid;
ST col[30007];
 
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 7 ms 35664 KB Output is correct
2 Correct 8 ms 35920 KB Output is correct
3 Correct 8 ms 35920 KB Output is correct
4 Correct 7 ms 35664 KB Output is correct
5 Correct 6 ms 35592 KB Output is correct
6 Correct 9 ms 35920 KB Output is correct
7 Correct 7 ms 35664 KB Output is correct
8 Correct 6 ms 35664 KB Output is correct
9 Correct 8 ms 35920 KB Output is correct
10 Correct 7 ms 35920 KB Output is correct
11 Correct 8 ms 35664 KB Output is correct
12 Correct 7 ms 35664 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35664 KB Output is correct
2 Correct 7 ms 35684 KB Output is correct
3 Correct 7 ms 35664 KB Output is correct
4 Correct 663 ms 112672 KB Output is correct
5 Correct 562 ms 112660 KB Output is correct
6 Correct 665 ms 109580 KB Output is correct
7 Correct 638 ms 109072 KB Output is correct
8 Correct 432 ms 64828 KB Output is correct
9 Correct 626 ms 109260 KB Output is correct
10 Correct 595 ms 108844 KB Output is correct
11 Correct 6 ms 35664 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35664 KB Output is correct
2 Correct 8 ms 35920 KB Output is correct
3 Correct 9 ms 35920 KB Output is correct
4 Correct 6 ms 35596 KB Output is correct
5 Correct 7 ms 35640 KB Output is correct
6 Correct 9 ms 35920 KB Output is correct
7 Correct 6 ms 35664 KB Output is correct
8 Correct 7 ms 35664 KB Output is correct
9 Correct 9 ms 35920 KB Output is correct
10 Correct 7 ms 35920 KB Output is correct
11 Correct 8 ms 35664 KB Output is correct
12 Correct 935 ms 60048 KB Output is correct
13 Correct 1133 ms 47432 KB Output is correct
14 Correct 439 ms 36684 KB Output is correct
15 Correct 1310 ms 53072 KB Output is correct
16 Correct 448 ms 68416 KB Output is correct
17 Correct 855 ms 57152 KB Output is correct
18 Correct 1167 ms 69044 KB Output is correct
19 Correct 1127 ms 68936 KB Output is correct
20 Correct 1136 ms 68380 KB Output is correct
21 Correct 6 ms 35664 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35664 KB Output is correct
2 Correct 9 ms 35920 KB Output is correct
3 Correct 11 ms 35920 KB Output is correct
4 Correct 6 ms 35664 KB Output is correct
5 Correct 6 ms 35408 KB Output is correct
6 Correct 8 ms 35920 KB Output is correct
7 Correct 6 ms 35632 KB Output is correct
8 Correct 7 ms 35664 KB Output is correct
9 Correct 8 ms 35920 KB Output is correct
10 Correct 7 ms 35920 KB Output is correct
11 Correct 7 ms 35832 KB Output is correct
12 Correct 652 ms 112668 KB Output is correct
13 Correct 578 ms 112664 KB Output is correct
14 Correct 657 ms 109600 KB Output is correct
15 Correct 660 ms 109260 KB Output is correct
16 Correct 430 ms 64828 KB Output is correct
17 Correct 654 ms 106528 KB Output is correct
18 Correct 593 ms 108960 KB Output is correct
19 Correct 927 ms 59976 KB Output is correct
20 Correct 1118 ms 47432 KB Output is correct
21 Correct 430 ms 36684 KB Output is correct
22 Correct 1289 ms 52904 KB Output is correct
23 Correct 455 ms 68488 KB Output is correct
24 Correct 926 ms 57160 KB Output is correct
25 Correct 1262 ms 68680 KB Output is correct
26 Correct 1129 ms 68996 KB Output is correct
27 Correct 1065 ms 68368 KB Output is correct
28 Runtime error 535 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 6 ms 35664 KB Output is correct
2 Correct 9 ms 35920 KB Output is correct
3 Correct 9 ms 35920 KB Output is correct
4 Correct 6 ms 35684 KB Output is correct
5 Correct 7 ms 35408 KB Output is correct
6 Correct 8 ms 35920 KB Output is correct
7 Correct 7 ms 35664 KB Output is correct
8 Correct 6 ms 35664 KB Output is correct
9 Correct 10 ms 35920 KB Output is correct
10 Correct 7 ms 35920 KB Output is correct
11 Correct 8 ms 35664 KB Output is correct
12 Correct 676 ms 112512 KB Output is correct
13 Correct 542 ms 112444 KB Output is correct
14 Correct 661 ms 109452 KB Output is correct
15 Correct 657 ms 107228 KB Output is correct
16 Correct 504 ms 64800 KB Output is correct
17 Correct 705 ms 94364 KB Output is correct
18 Correct 657 ms 83616 KB Output is correct
19 Correct 954 ms 60032 KB Output is correct
20 Correct 1114 ms 47432 KB Output is correct
21 Correct 422 ms 36520 KB Output is correct
22 Correct 1274 ms 52904 KB Output is correct
23 Correct 443 ms 68484 KB Output is correct
24 Correct 864 ms 57160 KB Output is correct
25 Correct 1245 ms 68680 KB Output is correct
26 Correct 1138 ms 68892 KB Output is correct
27 Correct 1183 ms 68280 KB Output is correct
28 Runtime error 532 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -