oj.uz

Submission #703778

# Submission time Handle Problem Language Result Execution time Memory
703778 2023-02-28T11:17:39 Z TheSahib Game (IOI13_game) C++17
100 / 100
 4011 ms 228552 KB 
#include <bits/stdc++.h>
#include "game.h"

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = (1 << 30) - 1;
const int BRANCH_LOG = 2;
const int BRANCH = (1 << BRANCH_LOG);
const int TREE_SIZE = 22000 * (30 / BRANCH_LOG);


struct SegTree1D{
    int nxt = 0;
    vector<ll> tree;
    vector<int> L, R;

    ll ans = 0;

    SegTree1D(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
    }

    int addNode(){
        tree.emplace_back(0);
        L.emplace_back(0);
        R.emplace_back(0);
        return ++nxt;
    }

    void update(int node, int l, int r, int pos, ll val){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid){
            if(!L[node]) L[node] = addNode();
            update(L[node], l, mid, pos, val);
        }
        else{
            if(!R[node]) R[node] = addNode();
            update(R[node], mid + 1, r, pos, val);
        }
        tree[node] = 0;
        if(L[node]) tree[node] = gcd(tree[node], tree[L[node]]);
        if(R[node]) tree[node] = gcd(tree[node], tree[R[node]]);
    }
    void ask(int node, int l, int r, int ql, int qr){
        if(qr < l || r < ql){
            return;
        }
        if(ql <= l && r <= qr){
            ans = gcd(ans, tree[node]);
            return;
        }
        int mid = (l + r) / 2;
        if(L[node]) ask(L[node], l, mid, ql, qr);
        if(R[node]) ask(R[node], mid + 1, r, ql, qr);
    }
    ll ask(int ql, int qr){
        ans = 0;
        ask(0, 0, MAX, ql, qr);
        return ans;
    }
};

struct SegTree2D{
    ll ans = 0;

    int nxt = 0;
    SegTree1D tree[TREE_SIZE];
    int child[TREE_SIZE][BRANCH];
    
    SegTree2D(){
        memset(child, 0, sizeof(child));
    }

    void update(int node, int l, int r, int posY, int posX, ll val){
        if(l == r){
            tree[node].update(0, 0, MAX, posX, val);
            return;
        }
        int inc = (r - l + 1) >> BRANCH_LOG;

        int uChild = (posY - l) / inc;
        if(!child[node][uChild]) child[node][uChild] = ++nxt;
        update(child[node][uChild], l + uChild * inc, l + (uChild + 1) * inc- 1, posY, posX, val);

        ll a = 0;
        for (int i = 0; i < BRANCH; i++)
        {
            if(child[node][i]) a = gcd(a, tree[child[node][i]].ask(posX, posX));
        }
        
        tree[node].update(0, 0, MAX, posX, a);
    }
    void ask(int node, int l, int r, int qlY, int qrY, int qlX, int qrX){
        if(qrY < l || r < qlY){
            return;
        }
        if(qlY <= l && r <= qrY){
            ans = gcd(ans,  tree[node].ask(qlX, qrX));
            return;
        }
        int inc = (r - l + 1) >> BRANCH_LOG;
        int a = l;
        for (int i = 0; i < BRANCH; i++)
        {
            if(child[node][i]){
                ask(child[node][i], a, a + inc - 1, qlY, qrY, qlX, qrX);
            }
            a += inc;
        }
    }
    ll ask(int qlY, int qrY, int qlX, int qrX){
        ans = 0;
        ask(0, 0, MAX, qlY, qrY, qlX, qrX);
        return ans;
    }
};

SegTree2D tree;

void init(int R, int C){
    
}

void update(int P, int Q, ll K){
    tree.update(0, 0, MAX, P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return tree.ask(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 64828 KB Output is correct
2 Correct 64 ms 64896 KB Output is correct
3 Correct 68 ms 64880 KB Output is correct
4 Correct 59 ms 64800 KB Output is correct
5 Correct 61 ms 64844 KB Output is correct
6 Correct 56 ms 64984 KB Output is correct
7 Correct 55 ms 64876 KB Output is correct
8 Correct 68 ms 64868 KB Output is correct
9 Correct 57 ms 64996 KB Output is correct
10 Correct 73 ms 64872 KB Output is correct
11 Correct 58 ms 64844 KB Output is correct
12 Correct 55 ms 64836 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 64852 KB Output is correct
2 Correct 58 ms 64884 KB Output is correct
3 Correct 63 ms 64836 KB Output is correct
4 Correct 691 ms 83032 KB Output is correct
5 Correct 610 ms 83384 KB Output is correct
6 Correct 711 ms 80084 KB Output is correct
7 Correct 649 ms 79900 KB Output is correct
8 Correct 519 ms 74512 KB Output is correct
9 Correct 663 ms 80024 KB Output is correct
10 Correct 659 ms 79684 KB Output is correct
11 Correct 54 ms 64844 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 64880 KB Output is correct
2 Correct 57 ms 64904 KB Output is correct
3 Correct 66 ms 65000 KB Output is correct
4 Correct 57 ms 64792 KB Output is correct
5 Correct 57 ms 64760 KB Output is correct
6 Correct 56 ms 64948 KB Output is correct
7 Correct 58 ms 64844 KB Output is correct
8 Correct 66 ms 64812 KB Output is correct
9 Correct 59 ms 64992 KB Output is correct
10 Correct 68 ms 64824 KB Output is correct
11 Correct 60 ms 64860 KB Output is correct
12 Correct 1307 ms 74716 KB Output is correct
13 Correct 1808 ms 68640 KB Output is correct
14 Correct 472 ms 65940 KB Output is correct
15 Correct 2059 ms 70320 KB Output is correct
16 Correct 582 ms 74284 KB Output is correct
17 Correct 1010 ms 71424 KB Output is correct
18 Correct 1483 ms 74644 KB Output is correct
19 Correct 1322 ms 74776 KB Output is correct
20 Correct 1284 ms 74152 KB Output is correct
21 Correct 56 ms 64876 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 64876 KB Output is correct
2 Correct 72 ms 64952 KB Output is correct
3 Correct 75 ms 65000 KB Output is correct
4 Correct 55 ms 64888 KB Output is correct
5 Correct 71 ms 64812 KB Output is correct
6 Correct 57 ms 64924 KB Output is correct
7 Correct 64 ms 64840 KB Output is correct
8 Correct 67 ms 64836 KB Output is correct
9 Correct 58 ms 64964 KB Output is correct
10 Correct 67 ms 64872 KB Output is correct
11 Correct 57 ms 64844 KB Output is correct
12 Correct 685 ms 83128 KB Output is correct
13 Correct 577 ms 83284 KB Output is correct
14 Correct 673 ms 80056 KB Output is correct
15 Correct 661 ms 79976 KB Output is correct
16 Correct 489 ms 74592 KB Output is correct
17 Correct 690 ms 80032 KB Output is correct
18 Correct 598 ms 79604 KB Output is correct
19 Correct 1317 ms 74912 KB Output is correct
20 Correct 1793 ms 68608 KB Output is correct
21 Correct 482 ms 65484 KB Output is correct
22 Correct 2113 ms 70392 KB Output is correct
23 Correct 613 ms 74260 KB Output is correct
24 Correct 1014 ms 71464 KB Output is correct
25 Correct 1459 ms 74712 KB Output is correct
26 Correct 1377 ms 74744 KB Output is correct
27 Correct 1334 ms 74212 KB Output is correct
28 Correct 702 ms 132276 KB Output is correct
29 Correct 1531 ms 141848 KB Output is correct
30 Correct 3218 ms 121700 KB Output is correct
31 Correct 2986 ms 110552 KB Output is correct
32 Correct 428 ms 65572 KB Output is correct
33 Correct 672 ms 66744 KB Output is correct
34 Correct 760 ms 139068 KB Output is correct
35 Correct 1123 ms 102936 KB Output is correct
36 Correct 2243 ms 139452 KB Output is correct
37 Correct 1768 ms 139580 KB Output is correct
38 Correct 1752 ms 139100 KB Output is correct
39 Correct 1534 ms 122316 KB Output is correct
40 Correct 55 ms 64872 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 64940 KB Output is correct
2 Correct 59 ms 64932 KB Output is correct
3 Correct 68 ms 64992 KB Output is correct
4 Correct 70 ms 64892 KB Output is correct
5 Correct 59 ms 64864 KB Output is correct
6 Correct 58 ms 64964 KB Output is correct
7 Correct 57 ms 65076 KB Output is correct
8 Correct 66 ms 64888 KB Output is correct
9 Correct 61 ms 64928 KB Output is correct
10 Correct 67 ms 65016 KB Output is correct
11 Correct 55 ms 64816 KB Output is correct
12 Correct 719 ms 82992 KB Output is correct
13 Correct 605 ms 83332 KB Output is correct
14 Correct 646 ms 80104 KB Output is correct
15 Correct 690 ms 80216 KB Output is correct
16 Correct 488 ms 74520 KB Output is correct
17 Correct 681 ms 79928 KB Output is correct
18 Correct 639 ms 79520 KB Output is correct
19 Correct 1286 ms 74812 KB Output is correct
20 Correct 1829 ms 68564 KB Output is correct
21 Correct 477 ms 65468 KB Output is correct
22 Correct 2072 ms 70352 KB Output is correct
23 Correct 592 ms 74188 KB Output is correct
24 Correct 987 ms 71540 KB Output is correct
25 Correct 1407 ms 74568 KB Output is correct
26 Correct 1312 ms 74864 KB Output is correct
27 Correct 1239 ms 74240 KB Output is correct
28 Correct 719 ms 132148 KB Output is correct
29 Correct 1626 ms 142120 KB Output is correct
30 Correct 3234 ms 121688 KB Output is correct
31 Correct 2947 ms 110568 KB Output is correct
32 Correct 423 ms 65552 KB Output is correct
33 Correct 660 ms 66732 KB Output is correct
34 Correct 726 ms 139272 KB Output is correct
35 Correct 1221 ms 103156 KB Output is correct
36 Correct 2108 ms 139212 KB Output is correct
37 Correct 1726 ms 139524 KB Output is correct
38 Correct 1685 ms 139164 KB Output is correct
39 Correct 1045 ms 206360 KB Output is correct
40 Correct 2444 ms 228552 KB Output is correct
41 Correct 4011 ms 181384 KB Output is correct
42 Correct 3777 ms 158460 KB Output is correct
43 Correct 1098 ms 226140 KB Output is correct
44 Correct 516 ms 65488 KB Output is correct
45 Correct 1402 ms 122480 KB Output is correct
46 Correct 2780 ms 226700 KB Output is correct
47 Correct 2848 ms 226760 KB Output is correct
48 Correct 2697 ms 226488 KB Output is correct
49 Correct 54 ms 64884 KB Output is correct