oj.uz

Submission #782148

# Submission time Handle Problem Language Result Execution time Memory
782148 2023-07-13T15:40:38 Z FatihSolak Game (IOI13_game) C++17
100 / 100
 2247 ms 155392 KB 
#include "game.h"
#include <bits/stdc++.h>
#define N 4000005
using namespace std;
int R,C;

struct node1{
    long long val;
    int l,r;
    int lc,rc;
    node1():lc(0),rc(0),val(0){

    }
}t1[N];
int cnt1 = 1;
struct SegTree{
    int root;
    SegTree():root(0){

    }
    void upd(int v,int pos,long long val){
        if(t1[v].l == t1[v].r){
            t1[v].val = val;
            return;
        }
        if(t1[v].lc != 0 && t1[t1[v].lc].l <= pos && pos <= t1[t1[v].lc].r){
            upd(t1[v].lc,pos,val);
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        if(t1[v].rc != 0 && t1[t1[v].rc].l <= pos && pos <= t1[t1[v].rc].r){
            upd(t1[v].rc,pos,val);
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        int tm = (t1[v].l + t1[v].r)/2;
        if(t1[v].lc == 0 && pos <= tm){
            t1[v].lc = cnt1++;
            t1[t1[v].lc].val = val;
            t1[t1[v].lc].l = pos;
            t1[t1[v].lc].r = pos; 
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        if(t1[v].rc == 0 && pos > tm){
            t1[v].rc = cnt1++;
            t1[t1[v].rc].val = val;
            t1[t1[v].rc].l = pos;
            t1[t1[v].rc].r = pos; 
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        if(pos <= tm){
            int tmp = t1[v].lc;
            t1[v].lc = cnt1++;
            t1[t1[v].lc].l = t1[v].l;
            t1[t1[v].lc].r = tm;
            while(1){
                int tmm = (t1[t1[v].lc].l + t1[t1[v].lc].r)/2;
                if(t1[tmp].r <= tmm && pos <= tmm){
                    t1[t1[v].lc].r = tmm;
                    continue;
                }
                if(t1[tmp].l > tmm && pos > tmm){
                    t1[t1[v].lc].l = tmm + 1;
                    continue;
                }
                break;
            }
            if(pos < t1[tmp].l){
                t1[t1[v].lc].lc = cnt1++;
                t1[t1[v].lc].rc = tmp;
                t1[t1[t1[v].lc].lc].val = val;
                t1[t1[t1[v].lc].lc].l = pos;
                t1[t1[t1[v].lc].lc].r = pos; 
            }
            else{
                t1[t1[v].lc].lc = tmp;   
                t1[t1[v].lc].rc = cnt1++;
                t1[t1[t1[v].lc].rc].val = val;
                t1[t1[t1[v].lc].rc].l = pos;
                t1[t1[t1[v].lc].rc].r = pos; 
            }
            t1[t1[v].lc].val = __gcd(t1[t1[t1[v].lc].lc].val,t1[t1[t1[v].lc].rc].val);
        }
        else{
            int tmp = t1[v].rc;
            t1[v].rc = cnt1++;
            t1[t1[v].rc].l = tm+1;
            t1[t1[v].rc].r = t1[v].r;
            while(1){
                int tmm = (t1[t1[v].rc].l + t1[t1[v].rc].r)/2;
                if(t1[tmp].r <= tmm && pos <= tmm){
                    t1[t1[v].rc].r = tmm;
                    continue;
                }
                if(t1[tmp].l > tmm && pos > tmm){
                    t1[t1[v].rc].l = tmm + 1;
                    continue;
                }
                break;
            }
            if(pos < t1[tmp].l){
                t1[t1[v].rc].lc = cnt1++;
                t1[t1[v].rc].rc = tmp;
                t1[t1[t1[v].rc].lc].val = val;
                t1[t1[t1[v].rc].lc].l = pos;
                t1[t1[t1[v].rc].lc].r = pos; 
            }
            else{
                t1[t1[v].rc].lc = tmp;   
                t1[t1[v].rc].rc = cnt1++;
                t1[t1[t1[v].rc].rc].val = val;
                t1[t1[t1[v].rc].rc].l = pos;
                t1[t1[t1[v].rc].rc].r = pos; 
            }
            t1[t1[v].rc].val = __gcd(t1[t1[t1[v].rc].lc].val,t1[t1[t1[v].rc].rc].val);
        }
        t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
    }
    long long get(int v,int l,int r){
        // cout << v << ' ' << l << ' ' << r << endl;
        // cout << t1[v].l << ' ' << t1[v].r << ' ' <<  t1[v].val << endl;
        if(v == 0 || t1[v].r < l || r < t1[v].l)
            return 0;
        if(l <= t1[v].l && t1[v].r <= r){
            return t1[v].val;
        }
        return __gcd(get(t1[v].lc,l,r),get(t1[v].rc,l,r));
    }
    void upd(int pos,long long val){
        if(root == 0){
            root = cnt1++;
            t1[root].l = 0;
            t1[root].r = C-1;
        }
        upd(root,pos,val);
    }
    long long get(int l,int r){
        //cout << "HEY" << endl;
        return get(root,l,r);
    }
};

struct Node2{
    int lc,rc;
    SegTree t;
    Node2():lc(0),rc(0){

    }
}t2[N];
int cnt2 = 1;
map<int,SegTree> mp;
struct SegTree2D{
    int root;
    SegTree2D():root(0){}

    void upd(int v,int tl,int tr,int pos1,int pos2){
        t2[v].t.upd(pos2,mp[pos2].get(tl,tr));
        if(tl == tr){
            return;
        }
        int tm = (tl + tr)/2;
        if(pos1 <= tm){
            if(t2[v].lc == 0)
                t2[v].lc = cnt2++;
            upd(t2[v].lc,tl,tm,pos1,pos2);
        }
        else{
            if(t2[v].rc == 0)
                t2[v].rc = cnt2++;
            upd(t2[v].rc,tm+1,tr,pos1,pos2);
        }
    }
    long long get(int v,int tl,int tr,int l1,int r1,int l2,int r2){
        //cout << v << ' ' << tl << ' ' << tr << endl;
        if(v == 0 || tr < l1 || r1 < tl){
            return 0;
        }
        if(l1 <= tl && tr <= r1){
            return t2[v].t.get(l2,r2);
        }
        int tm = (tl + tr)/2;
        return __gcd(get(t2[v].lc,tl,tm,l1,r1,l2,r2),get(t2[v].rc,tm+1,tr,l1,r1,l2,r2));
    }
    void upd(int pos1,int pos2){
        if(root == 0){
            root = cnt2++;
        }
        upd(root,0,R-1,pos1,pos2);
    }
    long long get(int l1,int r1,int l2,int r2){
        return get(root, 0, R-1, l1, r1, l2, r2);
    }
}tree;

void init(int r, int c) {
    R = 1e9;
    C = 1e9;
}
void update(int P, int Q, long long K) {
    mp[Q].upd(P,K);
    tree.upd(P,Q);
}

long long calculate(int P, int Q, int U, int V) {
    return tree.get(P,U,Q,V);
}

Compilation message

game.cpp: In constructor 'node1::node1()':
game.cpp:10:12: warning: 'node1::rc' will be initialized after [-Wreorder]
   10 |     int lc,rc;
      |            ^~
game.cpp:8:15: warning:   'long long int node1::val' [-Wreorder]
    8 |     long long val;
      |               ^~~
game.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     node1():lc(0),rc(0),val(0){
      |     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141096 KB Output is correct
2 Correct 57 ms 141096 KB Output is correct
3 Correct 61 ms 141320 KB Output is correct
4 Correct 57 ms 141180 KB Output is correct
5 Correct 58 ms 141168 KB Output is correct
6 Correct 59 ms 141124 KB Output is correct
7 Correct 62 ms 141084 KB Output is correct
8 Correct 58 ms 141180 KB Output is correct
9 Correct 62 ms 141260 KB Output is correct
10 Correct 57 ms 141188 KB Output is correct
11 Correct 58 ms 141180 KB Output is correct
12 Correct 58 ms 141172 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 141132 KB Output is correct
2 Correct 59 ms 141144 KB Output is correct
3 Correct 59 ms 141164 KB Output is correct
4 Correct 569 ms 150080 KB Output is correct
5 Correct 418 ms 149828 KB Output is correct
6 Correct 541 ms 147280 KB Output is correct
7 Correct 687 ms 147008 KB Output is correct
8 Correct 396 ms 147188 KB Output is correct
9 Correct 622 ms 147072 KB Output is correct
10 Correct 554 ms 146904 KB Output is correct
11 Correct 66 ms 141120 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 141112 KB Output is correct
2 Correct 58 ms 141064 KB Output is correct
3 Correct 58 ms 141088 KB Output is correct
4 Correct 57 ms 141184 KB Output is correct
5 Correct 61 ms 141256 KB Output is correct
6 Correct 60 ms 141148 KB Output is correct
7 Correct 59 ms 141184 KB Output is correct
8 Correct 59 ms 141184 KB Output is correct
9 Correct 57 ms 141096 KB Output is correct
10 Correct 60 ms 141064 KB Output is correct
11 Correct 65 ms 141180 KB Output is correct
12 Correct 598 ms 149392 KB Output is correct
13 Correct 993 ms 145752 KB Output is correct
14 Correct 344 ms 146424 KB Output is correct
15 Correct 1069 ms 146432 KB Output is correct
16 Correct 296 ms 146188 KB Output is correct
17 Correct 621 ms 147348 KB Output is correct
18 Correct 1033 ms 147640 KB Output is correct
19 Correct 835 ms 147772 KB Output is correct
20 Correct 769 ms 147248 KB Output is correct
21 Correct 60 ms 141260 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 141188 KB Output is correct
2 Correct 61 ms 141132 KB Output is correct
3 Correct 59 ms 141132 KB Output is correct
4 Correct 58 ms 141132 KB Output is correct
5 Correct 58 ms 141132 KB Output is correct
6 Correct 59 ms 141184 KB Output is correct
7 Correct 58 ms 141128 KB Output is correct
8 Correct 62 ms 141184 KB Output is correct
9 Correct 60 ms 141096 KB Output is correct
10 Correct 59 ms 141244 KB Output is correct
11 Correct 58 ms 141116 KB Output is correct
12 Correct 501 ms 150088 KB Output is correct
13 Correct 366 ms 149888 KB Output is correct
14 Correct 575 ms 147296 KB Output is correct
15 Correct 602 ms 147092 KB Output is correct
16 Correct 413 ms 147220 KB Output is correct
17 Correct 564 ms 147176 KB Output is correct
18 Correct 595 ms 146688 KB Output is correct
19 Correct 595 ms 149348 KB Output is correct
20 Correct 977 ms 145844 KB Output is correct
21 Correct 295 ms 146416 KB Output is correct
22 Correct 1096 ms 146432 KB Output is correct
23 Correct 290 ms 146124 KB Output is correct
24 Correct 631 ms 147352 KB Output is correct
25 Correct 957 ms 147584 KB Output is correct
26 Correct 841 ms 147672 KB Output is correct
27 Correct 837 ms 147192 KB Output is correct
28 Correct 350 ms 152700 KB Output is correct
29 Correct 878 ms 155296 KB Output is correct
30 Correct 1716 ms 149060 KB Output is correct
31 Correct 1581 ms 149096 KB Output is correct
32 Correct 316 ms 150880 KB Output is correct
33 Correct 395 ms 150852 KB Output is correct
34 Correct 219 ms 149140 KB Output is correct
35 Correct 671 ms 152540 KB Output is correct
36 Correct 1142 ms 153216 KB Output is correct
37 Correct 909 ms 153392 KB Output is correct
38 Correct 919 ms 152796 KB Output is correct
39 Correct 892 ms 153040 KB Output is correct
40 Correct 57 ms 141200 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 141180 KB Output is correct
2 Correct 57 ms 141068 KB Output is correct
3 Correct 58 ms 141136 KB Output is correct
4 Correct 65 ms 141132 KB Output is correct
5 Correct 58 ms 141164 KB Output is correct
6 Correct 58 ms 141184 KB Output is correct
7 Correct 58 ms 141068 KB Output is correct
8 Correct 64 ms 141208 KB Output is correct
9 Correct 59 ms 141132 KB Output is correct
10 Correct 60 ms 141172 KB Output is correct
11 Correct 58 ms 141168 KB Output is correct
12 Correct 519 ms 150060 KB Output is correct
13 Correct 367 ms 149812 KB Output is correct
14 Correct 544 ms 147256 KB Output is correct
15 Correct 610 ms 147012 KB Output is correct
16 Correct 394 ms 147204 KB Output is correct
17 Correct 570 ms 147084 KB Output is correct
18 Correct 544 ms 146912 KB Output is correct
19 Correct 605 ms 149408 KB Output is correct
20 Correct 1022 ms 145916 KB Output is correct
21 Correct 289 ms 146296 KB Output is correct
22 Correct 1077 ms 146420 KB Output is correct
23 Correct 294 ms 146220 KB Output is correct
24 Correct 630 ms 147392 KB Output is correct
25 Correct 974 ms 147540 KB Output is correct
26 Correct 849 ms 147744 KB Output is correct
27 Correct 801 ms 147088 KB Output is correct
28 Correct 335 ms 152644 KB Output is correct
29 Correct 915 ms 155392 KB Output is correct
30 Correct 1712 ms 148940 KB Output is correct
31 Correct 1501 ms 148940 KB Output is correct
32 Correct 313 ms 150856 KB Output is correct
33 Correct 391 ms 150788 KB Output is correct
34 Correct 220 ms 149072 KB Output is correct
35 Correct 652 ms 152440 KB Output is correct
36 Correct 1190 ms 153384 KB Output is correct
37 Correct 931 ms 153420 KB Output is correct
38 Correct 982 ms 152764 KB Output is correct
39 Correct 432 ms 153404 KB Output is correct
40 Correct 1378 ms 155368 KB Output is correct
41 Correct 2247 ms 149588 KB Output is correct
42 Correct 1997 ms 149392 KB Output is correct
43 Correct 309 ms 150180 KB Output is correct
44 Correct 372 ms 151348 KB Output is correct
45 Correct 837 ms 152948 KB Output is correct
46 Correct 1411 ms 154240 KB Output is correct
47 Correct 1449 ms 154260 KB Output is correct
48 Correct 1375 ms 153808 KB Output is correct
49 Correct 60 ms 141132 KB Output is correct