oj.uz

Submission #1101352

# Submission time Handle Problem Language Result Execution time Memory
1101352 2024-10-16T06:58:34 Z alexander707070 Game (IOI13_game) C++14
63 / 100
 1382 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,w;
    };
 
    vector<node> tree;
    int num;
 
    void init(){
        ST a,b,c,d;
        a.init(); b.init();
        c.init(); d.init();

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

        tree.push_back({0,0,a,b}); 
        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 1876 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 1 ms 1488 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 2 ms 1696 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1360 KB Output is correct
2 Correct 1 ms 1360 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 596 ms 82732 KB Output is correct
5 Correct 509 ms 82428 KB Output is correct
6 Correct 649 ms 79908 KB Output is correct
7 Correct 668 ms 79648 KB Output is correct
8 Correct 418 ms 35036 KB Output is correct
9 Correct 640 ms 79776 KB Output is correct
10 Correct 664 ms 79408 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1532 KB Output is correct
2 Correct 3 ms 1872 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 934 ms 30284 KB Output is correct
13 Correct 1090 ms 17124 KB Output is correct
14 Correct 427 ms 6988 KB Output is correct
15 Correct 1249 ms 23508 KB Output is correct
16 Correct 435 ms 38848 KB Output is correct
17 Correct 922 ms 28380 KB Output is correct
18 Correct 1382 ms 40472 KB Output is correct
19 Correct 1262 ms 40488 KB Output is correct
20 Correct 1163 ms 39976 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1360 KB Output is correct
2 Correct 3 ms 2040 KB Output is correct
3 Correct 4 ms 1740 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 3 ms 2040 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 3 ms 1364 KB Output is correct
12 Correct 620 ms 82852 KB Output is correct
13 Correct 522 ms 82212 KB Output is correct
14 Correct 641 ms 79908 KB Output is correct
15 Correct 616 ms 79636 KB Output is correct
16 Correct 416 ms 34904 KB Output is correct
17 Correct 617 ms 79716 KB Output is correct
18 Correct 615 ms 79400 KB Output is correct
19 Correct 913 ms 30392 KB Output is correct
20 Correct 1098 ms 17080 KB Output is correct
21 Correct 435 ms 6940 KB Output is correct
22 Correct 1235 ms 23464 KB Output is correct
23 Correct 413 ms 38840 KB Output is correct
24 Correct 929 ms 28344 KB Output is correct
25 Correct 1296 ms 40520 KB Output is correct
26 Correct 1182 ms 40608 KB Output is correct
27 Correct 1221 ms 39824 KB Output is correct
28 Runtime error 632 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 1876 KB Output is correct
4 Correct 2 ms 1552 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 1 ms 1464 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 687 ms 82996 KB Output is correct
13 Correct 574 ms 82348 KB Output is correct
14 Correct 640 ms 79880 KB Output is correct
15 Correct 626 ms 79504 KB Output is correct
16 Correct 411 ms 34880 KB Output is correct
17 Correct 602 ms 79784 KB Output is correct
18 Correct 621 ms 79320 KB Output is correct
19 Correct 950 ms 30392 KB Output is correct
20 Correct 1105 ms 17244 KB Output is correct
21 Correct 428 ms 7040 KB Output is correct
22 Correct 1274 ms 23576 KB Output is correct
23 Correct 443 ms 38980 KB Output is correct
24 Correct 945 ms 28336 KB Output is correct
25 Correct 1340 ms 40412 KB Output is correct
26 Correct 1258 ms 40600 KB Output is correct
27 Correct 1170 ms 39780 KB Output is correct
28 Runtime error 645 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -