oj.uz

Submission #1101354

# Submission time Handle Problem Language Result Execution time Memory
1101354 2024-10-16T07:00:29 Z alexander707070 Game (IOI13_game) C++14
63 / 100
 1313 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
 
#define MAXN 500007
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;
    };
 
    vector<node> tree;
    int num;
 
    void init(){
        ST a,b;
        a.init(); b.init();

        tree.push_back({0,0,a});
        tree.push_back({0,0,b});
        num=1;
    }
 
    void addnode(){ 
        ST a; a.init();

        tree.push_back({0,0,a}); 
        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 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 1360 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1872 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 3 ms 1872 KB Output is correct
7 Correct 1 ms 1468 KB Output is correct
8 Correct 1 ms 1528 KB Output is correct
9 Correct 3 ms 1668 KB Output is correct
10 Correct 2 ms 1616 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 1 ms 1360 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1360 KB Output is correct
2 Correct 1 ms 1360 KB Output is correct
3 Correct 1 ms 1360 KB Output is correct
4 Correct 590 ms 78360 KB Output is correct
5 Correct 495 ms 78420 KB Output is correct
6 Correct 660 ms 75288 KB Output is correct
7 Correct 651 ms 75048 KB Output is correct
8 Correct 422 ms 30524 KB Output is correct
9 Correct 625 ms 75032 KB Output is correct
10 Correct 610 ms 74756 KB Output is correct
11 Correct 1 ms 1360 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1528 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1872 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 3 ms 1872 KB Output is correct
7 Correct 2 ms 1360 KB Output is correct
8 Correct 1 ms 1360 KB Output is correct
9 Correct 3 ms 1616 KB Output is correct
10 Correct 3 ms 1616 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 917 ms 25928 KB Output is correct
13 Correct 1092 ms 13092 KB Output is correct
14 Correct 412 ms 2376 KB Output is correct
15 Correct 1202 ms 18976 KB Output is correct
16 Correct 413 ms 34396 KB Output is correct
17 Correct 920 ms 23112 KB Output is correct
18 Correct 1313 ms 34660 KB Output is correct
19 Correct 1175 ms 34940 KB Output is correct
20 Correct 1149 ms 34208 KB Output is correct
21 Correct 1 ms 1360 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1360 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1872 KB Output is correct
4 Correct 2 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 3 ms 1756 KB Output is correct
7 Correct 2 ms 1528 KB Output is correct
8 Correct 2 ms 1528 KB Output is correct
9 Correct 3 ms 1616 KB Output is correct
10 Correct 2 ms 1616 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 638 ms 78360 KB Output is correct
13 Correct 561 ms 78400 KB Output is correct
14 Correct 626 ms 75284 KB Output is correct
15 Correct 600 ms 74884 KB Output is correct
16 Correct 425 ms 30524 KB Output is correct
17 Correct 710 ms 75164 KB Output is correct
18 Correct 635 ms 74664 KB Output is correct
19 Correct 921 ms 25752 KB Output is correct
20 Correct 1092 ms 13128 KB Output is correct
21 Correct 398 ms 2376 KB Output is correct
22 Correct 1269 ms 18892 KB Output is correct
23 Correct 431 ms 34376 KB Output is correct
24 Correct 899 ms 23112 KB Output is correct
25 Correct 1225 ms 34756 KB Output is correct
26 Correct 1234 ms 34888 KB Output is correct
27 Correct 1202 ms 34320 KB Output is correct
28 Runtime error 650 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 2 ms 1360 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1872 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1360 KB Output is correct
6 Correct 3 ms 1872 KB Output is correct
7 Correct 2 ms 1360 KB Output is correct
8 Correct 2 ms 1360 KB Output is correct
9 Correct 3 ms 1616 KB Output is correct
10 Correct 2 ms 1616 KB Output is correct
11 Correct 2 ms 1360 KB Output is correct
12 Correct 667 ms 78440 KB Output is correct
13 Correct 521 ms 78244 KB Output is correct
14 Correct 611 ms 75292 KB Output is correct
15 Correct 634 ms 75068 KB Output is correct
16 Correct 439 ms 30524 KB Output is correct
17 Correct 627 ms 75056 KB Output is correct
18 Correct 596 ms 74652 KB Output is correct
19 Correct 921 ms 25928 KB Output is correct
20 Correct 1111 ms 13128 KB Output is correct
21 Correct 432 ms 2380 KB Output is correct
22 Correct 1212 ms 19016 KB Output is correct
23 Correct 426 ms 34376 KB Output is correct
24 Correct 867 ms 23112 KB Output is correct
25 Correct 1184 ms 34764 KB Output is correct
26 Correct 1161 ms 34780 KB Output is correct
27 Correct 1087 ms 34120 KB Output is correct
28 Runtime error 671 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -