oj.uz

Submission #566351

# Submission time Handle Problem Language Result Execution time Memory
566351 2022-05-22T09:09:52 Z pls33 Game (IOI13_game) C++17
100 / 100
 3471 ms 73296 KB 
#include "game.h"
#include <bits/stdc++.h>
    
using namespace std;
    
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
    
#pragma endregion
    
int64_t gcd2(int64_t x, int64_t y) {
    return !y ? x : gcd2(y, x % y);
}

int rnd() { 
    return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15));
}

struct tnode_t {
    tnode_t *l, *r;

    int pos, key, min, max;
    int64_t val, g;

    tnode_t(int position, int64_t value){
        l = nullptr;
        r = nullptr;
        
        pos = position;
        min = position;
        max = position;

        key = rnd();
        val = value;
        g = value;
    }

    void update(){
        g = val;
        if(l){
            g = gcd2(g, l->g);
        }
        if(r){
            g = gcd2(g, r->g);
        }

        min = l ? l->min : pos;
        max = r ? r->max : pos;
    }
};

struct treap_t {
    tnode_t *root;

    treap_t(){
        root = nullptr;
        srand(rnd());
    }

    void split(tnode_t *node, int pos, tnode_t* &l, tnode_t* &r){
        if(!node){
            l = nullptr;
            r = nullptr;

            return;
        }

        if(node->pos < pos){
            split(node->r, pos, l, r);

            node->r = l;
            l = node;
        }
        else {
            split(node->l, pos, l, r);
            node->l = r;
            r = node;
        }

        node->update();
    }

    tnode_t* merge(tnode_t *l, tnode_t *r){
        if(!l || !r){
            return l ? l : r;
        }

        if(l->key < r->key){
            l->r = merge(l->r, r);
            l->update();

            return l;
        }

        r->l = merge(l, r->l);
        r->update();

        return r;
    }

    bool find(int pos){
        tnode_t* node = root;
        while(node){
            if(node->pos == pos){
                return true;
            }

            if(node->pos > pos){
                node = node->l;
            }
            else {
                node = node->r;
            }
        }

        return false;
    }

    void update(tnode_t *node, int pos, int64_t val){
        if(node->pos == pos){
            node->val = val;
            node->update();

            return;
        }

        if(node->pos > pos){
            update(node->l, pos, val);
        }
        else {
            update(node->r, pos, val);
        }

        node->update();
    }

    void insert(int pos, int64_t val){
        if(find(pos)){
            update(root, pos, val);

            return;
        }

        tnode_t *l = nullptr, *r = nullptr;
        split(root, pos, l, r);

        tnode_t *merged_left = merge(l, new tnode_t(pos, val));
        root = merge(merged_left, r);
    }

    int64_t query(tnode_t *node, int left, int right){
        if(node->max < left || node->min > right){
            return 0;
        }
        
        if(left <= node->min && node->max <= right){
            return node->g;
        }

        int64_t res = (left <= node->pos && node->pos <= right) ? node->val : 0;
        if(node->l){
            res = gcd2(res, query(node->l, left, right));
        }
        if(node->r){
            res = gcd2(res, query(node->r, left, right));
        }

        return res;
    }

    int64_t query(int left, int right){
        if(!root){
            return 0;
        }

        return query(root, left, right);
    }
};

struct snode_t {
    snode_t *l, *r;
    treap_t treap;
    int left, right;

    snode_t(){
        l = nullptr;
        r = nullptr;
    }

    snode_t(int left_bound, int right_bound){
        l = nullptr;
        r = nullptr;

        left = left_bound;
        right = right_bound;
    }

    void add_left(){
        if(!l){
            l = new snode_t(left, (left + right) / 2);
        }
    }

    void add_right(){
        if(!r){
            r = new snode_t((left + right) / 2 + 1, right);
        }
    }

    void fix(int pos){
        int64_t val = 0;
        if(l){
            val = gcd2(val, l->treap.query(pos, pos));
        }
        if(r){
            val = gcd2(val, r->treap.query(pos, pos));
        }

        treap.insert(pos, val);
    }

    void update(int row, int col, int64_t val){
        if(right < row || row < left){
            return;
        }

        if(left == right){
            treap.insert(col, val);
            return;
        }

        if(row <= (left + right) / 2){
            add_left();
            l->update(row, col, val);
        }
        else {
            add_right();
            r->update(row, col, val);
        }

        fix(col);
    }

    int64_t query(int row0, int row1, int col0, int col1){
        if(row0 > right || row1 < left){
            return 0;
        }

        if(row0 <= left && right <= row1){
            return treap.query(col0, col1);
        }

        int64_t res = 0;
        if(l){
            res = gcd2(res, l->query(row0, row1, col0, col1));
        }
        if(r){
            res = gcd2(res, r->query(row0, row1, col0, col1));
        }

        return res;
    }
};

snode_t tree;

void init(int row_count, int col_count) {
    srand(12341234);

    tree = snode_t(0, row_count);
}
    
void update(int row, int col, long long val) {
    tree.update(row, col, val);
}
    
long long calculate(int row0, int col0, int row1, int col1) {
    return tree.query(row0, row1, col0, col1);
}

Compilation message

game.cpp:6: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    6 | #pragma region dalykai
      | 
game.cpp:30: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   30 | #pragma endregion
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 304 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 623 ms 11544 KB Output is correct
5 Correct 297 ms 11288 KB Output is correct
6 Correct 612 ms 8780 KB Output is correct
7 Correct 712 ms 8524 KB Output is correct
8 Correct 473 ms 7428 KB Output is correct
9 Correct 670 ms 8584 KB Output is correct
10 Correct 692 ms 8264 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 841 ms 13260 KB Output is correct
13 Correct 1282 ms 7616 KB Output is correct
14 Correct 234 ms 5584 KB Output is correct
15 Correct 1399 ms 9068 KB Output is correct
16 Correct 315 ms 11312 KB Output is correct
17 Correct 895 ms 9732 KB Output is correct
18 Correct 1636 ms 12752 KB Output is correct
19 Correct 1457 ms 12844 KB Output is correct
20 Correct 1259 ms 12276 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 533 ms 11552 KB Output is correct
13 Correct 386 ms 11276 KB Output is correct
14 Correct 671 ms 8756 KB Output is correct
15 Correct 731 ms 8448 KB Output is correct
16 Correct 433 ms 7492 KB Output is correct
17 Correct 708 ms 8544 KB Output is correct
18 Correct 648 ms 8176 KB Output is correct
19 Correct 807 ms 13312 KB Output is correct
20 Correct 1194 ms 7684 KB Output is correct
21 Correct 236 ms 5620 KB Output is correct
22 Correct 1301 ms 9020 KB Output is correct
23 Correct 284 ms 11412 KB Output is correct
24 Correct 760 ms 9752 KB Output is correct
25 Correct 1425 ms 12744 KB Output is correct
26 Correct 1199 ms 13052 KB Output is correct
27 Correct 1084 ms 12464 KB Output is correct
28 Correct 795 ms 38992 KB Output is correct
29 Correct 1385 ms 41696 KB Output is correct
30 Correct 1628 ms 29712 KB Output is correct
31 Correct 1515 ms 24596 KB Output is correct
32 Correct 308 ms 10168 KB Output is correct
33 Correct 428 ms 10580 KB Output is correct
34 Correct 707 ms 35436 KB Output is correct
35 Correct 1073 ms 25276 KB Output is correct
36 Correct 2295 ms 39512 KB Output is correct
37 Correct 1890 ms 39812 KB Output is correct
38 Correct 1982 ms 39264 KB Output is correct
39 Correct 1603 ms 32996 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 509 ms 11560 KB Output is correct
13 Correct 273 ms 11300 KB Output is correct
14 Correct 549 ms 8916 KB Output is correct
15 Correct 605 ms 8432 KB Output is correct
16 Correct 365 ms 7572 KB Output is correct
17 Correct 641 ms 8624 KB Output is correct
18 Correct 560 ms 8260 KB Output is correct
19 Correct 682 ms 13388 KB Output is correct
20 Correct 1084 ms 7756 KB Output is correct
21 Correct 226 ms 5524 KB Output is correct
22 Correct 1275 ms 9104 KB Output is correct
23 Correct 305 ms 11392 KB Output is correct
24 Correct 750 ms 9792 KB Output is correct
25 Correct 1251 ms 12772 KB Output is correct
26 Correct 1248 ms 12952 KB Output is correct
27 Correct 1239 ms 12452 KB Output is correct
28 Correct 828 ms 39076 KB Output is correct
29 Correct 1817 ms 41696 KB Output is correct
30 Correct 1922 ms 29708 KB Output is correct
31 Correct 1602 ms 24492 KB Output is correct
32 Correct 308 ms 10132 KB Output is correct
33 Correct 470 ms 10492 KB Output is correct
34 Correct 698 ms 35400 KB Output is correct
35 Correct 1156 ms 25280 KB Output is correct
36 Correct 2423 ms 39692 KB Output is correct
37 Correct 1870 ms 39716 KB Output is correct
38 Correct 1781 ms 39268 KB Output is correct
39 Correct 1230 ms 71476 KB Output is correct
40 Correct 2838 ms 73296 KB Output is correct
41 Correct 2739 ms 55272 KB Output is correct
42 Correct 2324 ms 43592 KB Output is correct
43 Correct 1477 ms 67912 KB Output is correct
44 Correct 398 ms 10624 KB Output is correct
45 Correct 1565 ms 33056 KB Output is correct
46 Correct 3471 ms 72036 KB Output is correct
47 Correct 3463 ms 72160 KB Output is correct
48 Correct 3465 ms 71788 KB Output is correct
49 Correct 1 ms 300 KB Output is correct