oj.uz

Submission #703768

# Submission time Handle Problem Language Result Execution time Memory
703768 2023-02-28T09:55:26 Z TheSahib Game (IOI13_game) C++17
100 / 100
 9813 ms 111848 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 = 5;
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;
    
    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]]);
    }
    ll ask(int node, int l, int r, int ql, int qr){
        if(qr < l || r < ql){
            return 0;
        }
        if(ql <= l && r <= qr){
            return tree[node];
        }
        int mid = (l + r) / 2;
        ll ans = 0;
        if(L[node]) ans = gcd(ans, ask(L[node], l, mid, ql, qr));
        if(R[node]) ans = gcd(ans, ask(R[node], mid + 1, r, ql, qr));
        return ans;
    }
};

struct SegTree2D{
    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;
        }
        ll ans = 0;
        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);

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 39464 KB Output is correct
2 Correct 29 ms 39536 KB Output is correct
3 Correct 30 ms 39548 KB Output is correct
4 Correct 29 ms 39688 KB Output is correct
5 Correct 28 ms 39540 KB Output is correct
6 Correct 30 ms 39596 KB Output is correct
7 Correct 27 ms 39508 KB Output is correct
8 Correct 27 ms 39524 KB Output is correct
9 Correct 28 ms 39500 KB Output is correct
10 Correct 29 ms 39548 KB Output is correct
11 Correct 29 ms 39520 KB Output is correct
12 Correct 28 ms 39468 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 39520 KB Output is correct
2 Correct 28 ms 39468 KB Output is correct
3 Correct 28 ms 39500 KB Output is correct
4 Correct 785 ms 50840 KB Output is correct
5 Correct 528 ms 51056 KB Output is correct
6 Correct 656 ms 47736 KB Output is correct
7 Correct 671 ms 47444 KB Output is correct
8 Correct 493 ms 45760 KB Output is correct
9 Correct 681 ms 47532 KB Output is correct
10 Correct 610 ms 47200 KB Output is correct
11 Correct 28 ms 39508 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 39480 KB Output is correct
2 Correct 29 ms 39520 KB Output is correct
3 Correct 29 ms 39620 KB Output is correct
4 Correct 29 ms 39484 KB Output is correct
5 Correct 28 ms 39500 KB Output is correct
6 Correct 30 ms 39572 KB Output is correct
7 Correct 28 ms 39496 KB Output is correct
8 Correct 31 ms 39512 KB Output is correct
9 Correct 31 ms 39636 KB Output is correct
10 Correct 28 ms 39548 KB Output is correct
11 Correct 28 ms 39540 KB Output is correct
12 Correct 3211 ms 47160 KB Output is correct
13 Correct 4382 ms 42588 KB Output is correct
14 Correct 480 ms 40812 KB Output is correct
15 Correct 6221 ms 43596 KB Output is correct
16 Correct 2206 ms 45472 KB Output is correct
17 Correct 1968 ms 44168 KB Output is correct
18 Correct 3211 ms 45952 KB Output is correct
19 Correct 2682 ms 46092 KB Output is correct
20 Correct 2669 ms 45440 KB Output is correct
21 Correct 31 ms 39480 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 39512 KB Output is correct
2 Correct 30 ms 39636 KB Output is correct
3 Correct 32 ms 39556 KB Output is correct
4 Correct 30 ms 39508 KB Output is correct
5 Correct 36 ms 39660 KB Output is correct
6 Correct 37 ms 39536 KB Output is correct
7 Correct 31 ms 39508 KB Output is correct
8 Correct 30 ms 39460 KB Output is correct
9 Correct 30 ms 39608 KB Output is correct
10 Correct 32 ms 39508 KB Output is correct
11 Correct 30 ms 39508 KB Output is correct
12 Correct 796 ms 50744 KB Output is correct
13 Correct 526 ms 51164 KB Output is correct
14 Correct 658 ms 47756 KB Output is correct
15 Correct 671 ms 47592 KB Output is correct
16 Correct 479 ms 45576 KB Output is correct
17 Correct 673 ms 47448 KB Output is correct
18 Correct 630 ms 47140 KB Output is correct
19 Correct 3275 ms 47104 KB Output is correct
20 Correct 4412 ms 42504 KB Output is correct
21 Correct 488 ms 40660 KB Output is correct
22 Correct 6118 ms 43564 KB Output is correct
23 Correct 2253 ms 45444 KB Output is correct
24 Correct 1918 ms 44092 KB Output is correct
25 Correct 3092 ms 45788 KB Output is correct
26 Correct 2653 ms 46072 KB Output is correct
27 Correct 2585 ms 45460 KB Output is correct
28 Correct 663 ms 69844 KB Output is correct
29 Correct 2763 ms 75716 KB Output is correct
30 Correct 7727 ms 65696 KB Output is correct
31 Correct 6950 ms 61156 KB Output is correct
32 Correct 389 ms 41332 KB Output is correct
33 Correct 616 ms 42080 KB Output is correct
34 Correct 2054 ms 73032 KB Output is correct
35 Correct 1474 ms 57756 KB Output is correct
36 Correct 3122 ms 73120 KB Output is correct
37 Correct 2320 ms 73432 KB Output is correct
38 Correct 2365 ms 72536 KB Output is correct
39 Correct 1891 ms 66428 KB Output is correct
40 Correct 29 ms 39552 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 39496 KB Output is correct
2 Correct 29 ms 39540 KB Output is correct
3 Correct 29 ms 39568 KB Output is correct
4 Correct 27 ms 39504 KB Output is correct
5 Correct 27 ms 39508 KB Output is correct
6 Correct 29 ms 39536 KB Output is correct
7 Correct 27 ms 39472 KB Output is correct
8 Correct 28 ms 39500 KB Output is correct
9 Correct 32 ms 39568 KB Output is correct
10 Correct 29 ms 39572 KB Output is correct
11 Correct 28 ms 39588 KB Output is correct
12 Correct 779 ms 50836 KB Output is correct
13 Correct 528 ms 51248 KB Output is correct
14 Correct 623 ms 47740 KB Output is correct
15 Correct 672 ms 47396 KB Output is correct
16 Correct 491 ms 45656 KB Output is correct
17 Correct 667 ms 47508 KB Output is correct
18 Correct 610 ms 47012 KB Output is correct
19 Correct 3182 ms 47164 KB Output is correct
20 Correct 4291 ms 42496 KB Output is correct
21 Correct 468 ms 40656 KB Output is correct
22 Correct 6030 ms 43444 KB Output is correct
23 Correct 2221 ms 45744 KB Output is correct
24 Correct 1908 ms 44116 KB Output is correct
25 Correct 2996 ms 45856 KB Output is correct
26 Correct 2636 ms 45932 KB Output is correct
27 Correct 2626 ms 45324 KB Output is correct
28 Correct 669 ms 69916 KB Output is correct
29 Correct 2646 ms 75996 KB Output is correct
30 Correct 7596 ms 65680 KB Output is correct
31 Correct 7020 ms 61124 KB Output is correct
32 Correct 394 ms 41436 KB Output is correct
33 Correct 618 ms 41932 KB Output is correct
34 Correct 2000 ms 73204 KB Output is correct
35 Correct 1487 ms 57904 KB Output is correct
36 Correct 2958 ms 73092 KB Output is correct
37 Correct 2314 ms 73336 KB Output is correct
38 Correct 2390 ms 72648 KB Output is correct
39 Correct 932 ms 102104 KB Output is correct
40 Correct 4046 ms 111848 KB Output is correct
41 Correct 9813 ms 91136 KB Output is correct
42 Correct 8926 ms 81904 KB Output is correct
43 Correct 2293 ms 110260 KB Output is correct
44 Correct 511 ms 41300 KB Output is correct
45 Correct 1921 ms 66168 KB Output is correct
46 Correct 4029 ms 110388 KB Output is correct
47 Correct 3974 ms 110660 KB Output is correct
48 Correct 3950 ms 109744 KB Output is correct
49 Correct 30 ms 39500 KB Output is correct