oj.uz

Submission #1101492

# Submission time Handle Problem Language Result Execution time Memory
1101492 2024-10-16T09:06:46 Z alexander707070 Game (IOI13_game) C++14
80 / 100
 2498 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
 
#define MAXN 25007
using namespace std;
 
const int maxs=1e9;

unordered_map<int,int> mp;

struct node{
    int l,r;
    long long val;
};

int num;
node tree[400*MAXN];

struct ST{

    int root;

    void init(){
        num++;
        root=num;
    }

    void addnode(){
        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;

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

            tree[v].val=__gcd(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 __gcd( 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];
    vector< pair<int,long long> > w[35*MAXN];
    int num;
 
    void init(){
        tree[1].t.init();
        num=1;
    }
 
    void addnode(){
        num++;
        tree[num].t.init();
    }
 
    void update(int v,int l,int r,int posx,int posy,long long val){
        if(l==r){
            if(w[v].empty()){
                w[v].push_back({posy,val});
                return;
            }

            for(int i=0;i<w[v].size();i++){
                if(w[v][i].first==posy)w[v][i].second=val;
                else if(i==w[v].size()-1){
                    w[v].push_back({posy,val});
                    break;
                }
            }

        }else{
            int tt=(l+r)/2;

            if(posx<=tt){
                if(tree[v].l==0){
                    addnode(); tree[v].l=num;
                }
                update(tree[v].l,l,tt,posx,posy,val);
            }else{
                if(tree[v].r==0){
                    addnode(); tree[v].r=num;
                }
                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){
            if(l!=r)return tree[v].t.query(ly,ry);
            else{
                long long res=0;
                for(int i=0;i<w[v].size();i++){
                    if(w[v][i].first<ly or w[v][i].first>ry)continue;
                    res=__gcd(res,w[v][i].second);
                }

                return res;
            }
        }else{
            int tt=(l+r)/2;
            return __gcd( 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;
}*/

Compilation message

game.cpp: In member function 'void ST2D::update(int, int, int, int, int, long long int)':
game.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int i=0;i<w[v].size();i++){
      |                         ~^~~~~~~~~~~~
game.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 else if(i==w[v].size()-1){
      |                         ~^~~~~~~~~~~~~~~
game.cpp: In member function 'long long int ST2D::getgcd(int, int, int, int, int, int, int)':
game.cpp:139:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                 for(int i=0;i<w[v].size();i++){
      |                             ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22864 KB Output is correct
2 Correct 6 ms 23120 KB Output is correct
3 Correct 5 ms 23120 KB Output is correct
4 Correct 4 ms 23008 KB Output is correct
5 Correct 4 ms 22864 KB Output is correct
6 Correct 5 ms 23120 KB Output is correct
7 Correct 4 ms 22864 KB Output is correct
8 Correct 4 ms 24912 KB Output is correct
9 Correct 5 ms 23120 KB Output is correct
10 Correct 4 ms 22864 KB Output is correct
11 Correct 4 ms 24912 KB Output is correct
12 Correct 4 ms 22864 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23040 KB Output is correct
2 Correct 5 ms 22864 KB Output is correct
3 Correct 5 ms 22864 KB Output is correct
4 Correct 1162 ms 53832 KB Output is correct
5 Correct 897 ms 54512 KB Output is correct
6 Correct 965 ms 51356 KB Output is correct
7 Correct 1425 ms 50688 KB Output is correct
8 Correct 453 ms 39756 KB Output is correct
9 Correct 1180 ms 51016 KB Output is correct
10 Correct 1265 ms 50632 KB Output is correct
11 Correct 4 ms 22864 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22864 KB Output is correct
2 Correct 7 ms 23120 KB Output is correct
3 Correct 5 ms 23120 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 22864 KB Output is correct
6 Correct 5 ms 23204 KB Output is correct
7 Correct 4 ms 22864 KB Output is correct
8 Correct 4 ms 24912 KB Output is correct
9 Correct 5 ms 23120 KB Output is correct
10 Correct 5 ms 22984 KB Output is correct
11 Correct 5 ms 25080 KB Output is correct
12 Correct 777 ms 34476 KB Output is correct
13 Correct 1102 ms 27976 KB Output is correct
14 Correct 437 ms 25672 KB Output is correct
15 Correct 1216 ms 32328 KB Output is correct
16 Correct 338 ms 35144 KB Output is correct
17 Correct 719 ms 32628 KB Output is correct
18 Correct 960 ms 36680 KB Output is correct
19 Correct 945 ms 35656 KB Output is correct
20 Correct 881 ms 34888 KB Output is correct
21 Correct 4 ms 22864 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22864 KB Output is correct
2 Correct 5 ms 23120 KB Output is correct
3 Correct 5 ms 23120 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 22864 KB Output is correct
6 Correct 5 ms 23120 KB Output is correct
7 Correct 4 ms 22864 KB Output is correct
8 Correct 5 ms 24912 KB Output is correct
9 Correct 5 ms 23120 KB Output is correct
10 Correct 4 ms 22864 KB Output is correct
11 Correct 5 ms 24912 KB Output is correct
12 Correct 1144 ms 53868 KB Output is correct
13 Correct 871 ms 54540 KB Output is correct
14 Correct 871 ms 51356 KB Output is correct
15 Correct 1324 ms 50780 KB Output is correct
16 Correct 452 ms 39832 KB Output is correct
17 Correct 1204 ms 50900 KB Output is correct
18 Correct 1256 ms 50520 KB Output is correct
19 Correct 731 ms 34500 KB Output is correct
20 Correct 1093 ms 27976 KB Output is correct
21 Correct 433 ms 25664 KB Output is correct
22 Correct 1229 ms 32192 KB Output is correct
23 Correct 361 ms 35144 KB Output is correct
24 Correct 731 ms 32584 KB Output is correct
25 Correct 969 ms 36680 KB Output is correct
26 Correct 915 ms 35728 KB Output is correct
27 Correct 883 ms 34980 KB Output is correct
28 Correct 442 ms 149068 KB Output is correct
29 Correct 1025 ms 164168 KB Output is correct
30 Correct 2405 ms 126024 KB Output is correct
31 Correct 2470 ms 102364 KB Output is correct
32 Correct 421 ms 23756 KB Output is correct
33 Correct 463 ms 25164 KB Output is correct
34 Correct 318 ms 161360 KB Output is correct
35 Correct 926 ms 94440 KB Output is correct
36 Correct 1631 ms 161756 KB Output is correct
37 Correct 1350 ms 161880 KB Output is correct
38 Correct 1319 ms 161352 KB Output is correct
39 Correct 1093 ms 130180 KB Output is correct
40 Correct 5 ms 22864 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22864 KB Output is correct
2 Correct 8 ms 23196 KB Output is correct
3 Correct 6 ms 23000 KB Output is correct
4 Correct 5 ms 23004 KB Output is correct
5 Correct 4 ms 22864 KB Output is correct
6 Correct 5 ms 23120 KB Output is correct
7 Correct 4 ms 22864 KB Output is correct
8 Correct 4 ms 24912 KB Output is correct
9 Correct 5 ms 22996 KB Output is correct
10 Correct 5 ms 23120 KB Output is correct
11 Correct 5 ms 25080 KB Output is correct
12 Correct 1187 ms 53832 KB Output is correct
13 Correct 913 ms 54600 KB Output is correct
14 Correct 941 ms 51380 KB Output is correct
15 Correct 1427 ms 50648 KB Output is correct
16 Correct 507 ms 39780 KB Output is correct
17 Correct 1234 ms 51016 KB Output is correct
18 Correct 1339 ms 50480 KB Output is correct
19 Correct 862 ms 34348 KB Output is correct
20 Correct 1142 ms 27972 KB Output is correct
21 Correct 475 ms 25868 KB Output is correct
22 Correct 1260 ms 32072 KB Output is correct
23 Correct 388 ms 35456 KB Output is correct
24 Correct 781 ms 32672 KB Output is correct
25 Correct 1123 ms 36644 KB Output is correct
26 Correct 1073 ms 35620 KB Output is correct
27 Correct 979 ms 34968 KB Output is correct
28 Correct 511 ms 149192 KB Output is correct
29 Correct 1112 ms 164324 KB Output is correct
30 Correct 2498 ms 126108 KB Output is correct
31 Correct 2399 ms 102384 KB Output is correct
32 Correct 410 ms 23880 KB Output is correct
33 Correct 430 ms 25160 KB Output is correct
34 Correct 303 ms 161352 KB Output is correct
35 Correct 754 ms 94392 KB Output is correct
36 Correct 1357 ms 161588 KB Output is correct
37 Correct 1174 ms 161756 KB Output is correct
38 Correct 1178 ms 161180 KB Output is correct
39 Runtime error 797 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -