oj.uz

Submission #1101358

# Submission time Handle Problem Language Result Execution time Memory
1101358 2024-10-16T07:07:27 Z alexander707070 Game (IOI13_game) C++14
63 / 100
 1260 ms 253000 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[300*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 1 ms 2384 KB Output is correct
2 Correct 2 ms 2808 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 1 ms 2384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2552 KB Output is correct
4 Correct 520 ms 53888 KB Output is correct
5 Correct 431 ms 52552 KB Output is correct
6 Correct 526 ms 49792 KB Output is correct
7 Correct 580 ms 49480 KB Output is correct
8 Correct 400 ms 31056 KB Output is correct
9 Correct 558 ms 49892 KB Output is correct
10 Correct 527 ms 49332 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 2652 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 930 ms 20472 KB Output is correct
13 Correct 1090 ms 10824 KB Output is correct
14 Correct 424 ms 3144 KB Output is correct
15 Correct 1210 ms 15424 KB Output is correct
16 Correct 409 ms 25264 KB Output is correct
17 Correct 832 ms 18212 KB Output is correct
18 Correct 1196 ms 25596 KB Output is correct
19 Correct 1060 ms 26340 KB Output is correct
20 Correct 1061 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 2808 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 2808 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 549 ms 54088 KB Output is correct
13 Correct 422 ms 52552 KB Output is correct
14 Correct 549 ms 49768 KB Output is correct
15 Correct 626 ms 49480 KB Output is correct
16 Correct 397 ms 30832 KB Output is correct
17 Correct 550 ms 49684 KB Output is correct
18 Correct 502 ms 49292 KB Output is correct
19 Correct 882 ms 20324 KB Output is correct
20 Correct 1105 ms 10828 KB Output is correct
21 Correct 403 ms 3144 KB Output is correct
22 Correct 1229 ms 15440 KB Output is correct
23 Correct 403 ms 25128 KB Output is correct
24 Correct 847 ms 18132 KB Output is correct
25 Correct 1260 ms 25416 KB Output is correct
26 Correct 1087 ms 26376 KB Output is correct
27 Correct 1022 ms 25740 KB Output is correct
28 Runtime error 365 ms 252744 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 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 1 ms 2640 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 529 ms 53876 KB Output is correct
13 Correct 448 ms 52552 KB Output is correct
14 Correct 553 ms 49832 KB Output is correct
15 Correct 585 ms 49480 KB Output is correct
16 Correct 426 ms 31064 KB Output is correct
17 Correct 589 ms 49788 KB Output is correct
18 Correct 528 ms 49344 KB Output is correct
19 Correct 892 ms 20296 KB Output is correct
20 Correct 1093 ms 10744 KB Output is correct
21 Correct 424 ms 3144 KB Output is correct
22 Correct 1229 ms 15432 KB Output is correct
23 Correct 419 ms 25272 KB Output is correct
24 Correct 901 ms 18248 KB Output is correct
25 Correct 1240 ms 25512 KB Output is correct
26 Correct 1101 ms 26184 KB Output is correct
27 Correct 1062 ms 27776 KB Output is correct
28 Runtime error 372 ms 253000 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -