oj.uz

Submission #681158

# Submission time Handle Problem Language Result Execution time Memory
681158 2023-01-12T12:53:22 Z nutella Game (IOI13_game) C++17
100 / 100
 7299 ms 15156 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#include "game.h"

using namespace std;
using ll = long long;

constexpr int MAXQ = 22001;

#define left lft
#define right rght
//#define gcd my_gcd

ll my_gcd(ll a, ll b) {
    if (!a || !b) return a ^ b;
    ll c;
    while ((c = a % b)) {
        a = b;
        b = c;
    }
    return b;
}

int R, C;

constexpr int M = MAXQ * 30 + 10;

int counter = 1;

ll d[M];

int left[M], right[M];

//vector<ll> d{{}};
//vector<int> left{{}}, right{{}};

int st_create() {
//    d.emplace_back(), left.emplace_back(), right.emplace_back();
    d[counter] = left[counter] = right[counter] = 0;
    return counter++;
}

void st_update(int v, int i, ll k, int l, int r) {
    while (l + 1 < r) {
        d[v] = gcd(d[v], k);
        int mid = (l + r) >> 1;
        if (i < mid) {
            if (!left[v]) {
                left[v] = st_create();
            }
            v = left[v];
            r = mid;
        } else {
            if (!right[v]) {
                right[v] = st_create();
            }
            v = right[v];
            l = mid;
        }
    }
    d[v] = gcd(d[v], k);
}

ll st_query(int v, int lx, int rx, int l, int r) {
    if (lx >= r || rx <= l) {
        return 0;
    } else if (lx <= l && r <= rx) {
        return d[v];
    } else {
        int mid = (l + r) >> 1;

        ll ans = 0;

        if (left[v]) {
            ans = st_query(left[v], lx, rx, l, mid);
        }
        if (right[v]) {
            ans = gcd(ans, st_query(right[v], lx, rx, mid, r));
        }

        return ans;
    }
}

void clear(int v) {
    if (!v) return;
    d[v] = 0;
    clear(left[v]);
    clear(right[v]);
}

constexpr int B = 250;

map<pair<int, int>, ll> mp;

constexpr int maxK = MAXQ / B + 1;

pair<int, int> l[maxK], r[maxK];
int root[maxK], top = 0;
vector<pair<int, int>> keks[maxK];
vector<ll> vals[maxK];

void rebuild() {
    counter = 1;

    top = 0;

    int last_sz = 0;
    for (auto [xx, k]: mp) {
        auto [x, y] = xx;
        if (last_sz == B) {
            last_sz = 0;
        }
        if (last_sz == 0) {
            l[top] = xx;
            r[top] = xx;
            keks[top].clear(), vals[top].clear();
            root[top++] = st_create();
        } else {
            r[top - 1] = xx;
        }
        keks[top - 1].push_back(xx);
        vals[top - 1].push_back(k);
        last_sz += 1;

        st_update(root[top - 1], y, k, 0, C);
    }
}

int last_rebuild = 0;

void insert(pair<int, int> xx, ll k) {
    auto itt = mp.find(xx);
    bool was = false;
    ll last = -1;
    if (itt != mp.end()) {
        was = true;
        last = itt->second;
    }
    mp[xx] = k;

    ++last_rebuild;

    if (last_rebuild == 2 * B) {
        last_rebuild = 0;
        rebuild();
        return;
    }

    int i = -1;
    if (xx >= r[top - 1]) {
        i = top - 1;
    } else if (xx <= l[0]) {
        i = 0;
    } else {
        for (int j = top - 1; j >= 0; --j) {
            if (l[j] <= xx) {
                i = j;
                break;
            }
        }
    }

    assert(i != -1);

    l[i] = min(l[i], xx);
    r[i] = max(r[i], xx);


    if (!was) {
        auto it = std::lower_bound(keks[i].begin(), keks[i].end(), xx);
        vals[i].insert(vals[i].begin() + (it - keks[i].begin()), k);
        keks[i].insert(it, xx);
    }

    auto it = std::lower_bound(keks[i].begin(), keks[i].end(),xx) - keks[i].begin();
    vals[i][it] = k;

    if (was) {
        clear(root[i]);
        for (int ii = 0; ii < keks[i].size(); ++ii) {
            st_update(root[i], keks[i][ii].second, vals[i][ii], 0, C);
        }
    } else {
        st_update(root[i], xx.second, k, 0, C);
    }
}

void init(int R, int C) {
    ::R = R, ::C = C;

    l[0] = {R + 1, C + 1}, r[0] = {0, 0};
    root[top++] = st_create();
}

void update(int P, int Q, ll K) {
    insert({P, Q}, K);
}

ll calculate(int P, int Q, int U, int V) {
    ll cd = 0;
//    pair<int, int> min_done = {U, V + 1};
//    pair<int, int> max_done = {P, Q - 1};
    int fi = 0, la = 0;
    for (int i = 0; i < top; ++i) {
        if (l[i].first >= P && r[i].first <= U) {
            cd = gcd(cd, st_query(root[i], Q, V + 1, 0, C));
//            min_done = min(min_done, l[i]);
//            max_done = max(max_done, r[i]);
        } else {
            if (l[i] <= pair{P, Q} && r[i] >= pair{P, Q}) {
                fi = i;
            }
            if (l[i] <= pair{U, V} && r[i] >= pair{U, V}) {
                la = i;
            }
        }
    }
    if (la == fi) la = -1;
    for (int k : {la, fi}) {
        if (k != -1) {
            for (int i = 0; i < keks[k].size(); ++i) {
                if (keks[k][i].first >= P && keks[k][i].first <= U && keks[k][i].second >= Q && keks[k][i].second <= V) {
                    cd = gcd(cd, vals[k][i]);
                }
            }
        }
    }

    return cd;
}

Compilation message

game.cpp: In function 'void insert(std::pair<int, int>, ll)':
game.cpp:182:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |         for (int ii = 0; ii < keks[i].size(); ++ii) {
      |                          ~~~^~~~~~~~~~~~~~~~
game.cpp:136:8: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  136 |     ll last = -1;
      |        ^~~~
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:223:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |             for (int i = 0; i < keks[k].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 308 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 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1521 ms 7608 KB Output is correct
5 Correct 1186 ms 8024 KB Output is correct
6 Correct 776 ms 5272 KB Output is correct
7 Correct 860 ms 4996 KB Output is correct
8 Correct 435 ms 4276 KB Output is correct
9 Correct 768 ms 5208 KB Output is correct
10 Correct 851 ms 4604 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 312 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1762 ms 6872 KB Output is correct
13 Correct 2626 ms 2952 KB Output is correct
14 Correct 874 ms 2644 KB Output is correct
15 Correct 2780 ms 3528 KB Output is correct
16 Correct 1303 ms 3956 KB Output is correct
17 Correct 654 ms 4304 KB Output is correct
18 Correct 1199 ms 4972 KB Output is correct
19 Correct 951 ms 5212 KB Output is correct
20 Correct 885 ms 4456 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 232 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 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 312 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1525 ms 7432 KB Output is correct
13 Correct 1164 ms 8020 KB Output is correct
14 Correct 779 ms 5360 KB Output is correct
15 Correct 838 ms 5092 KB Output is correct
16 Correct 434 ms 4240 KB Output is correct
17 Correct 772 ms 5212 KB Output is correct
18 Correct 854 ms 4856 KB Output is correct
19 Correct 1741 ms 7024 KB Output is correct
20 Correct 2632 ms 3128 KB Output is correct
21 Correct 869 ms 2528 KB Output is correct
22 Correct 2781 ms 3636 KB Output is correct
23 Correct 1311 ms 3956 KB Output is correct
24 Correct 634 ms 4256 KB Output is correct
25 Correct 1184 ms 5068 KB Output is correct
26 Correct 961 ms 5104 KB Output is correct
27 Correct 888 ms 4620 KB Output is correct
28 Correct 576 ms 6692 KB Output is correct
29 Correct 1939 ms 10820 KB Output is correct
30 Correct 4035 ms 5804 KB Output is correct
31 Correct 3502 ms 5408 KB Output is correct
32 Correct 1493 ms 3124 KB Output is correct
33 Correct 1874 ms 2968 KB Output is correct
34 Correct 1316 ms 7700 KB Output is correct
35 Correct 699 ms 5924 KB Output is correct
36 Correct 1359 ms 8028 KB Output is correct
37 Correct 1046 ms 8268 KB Output is correct
38 Correct 1008 ms 7744 KB Output is correct
39 Correct 910 ms 7136 KB Output is correct
40 Correct 1 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 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1502 ms 7532 KB Output is correct
13 Correct 1181 ms 8592 KB Output is correct
14 Correct 775 ms 5536 KB Output is correct
15 Correct 863 ms 5364 KB Output is correct
16 Correct 452 ms 5068 KB Output is correct
17 Correct 784 ms 6440 KB Output is correct
18 Correct 868 ms 4964 KB Output is correct
19 Correct 1710 ms 7820 KB Output is correct
20 Correct 2606 ms 3948 KB Output is correct
21 Correct 860 ms 2852 KB Output is correct
22 Correct 2765 ms 4240 KB Output is correct
23 Correct 1302 ms 4732 KB Output is correct
24 Correct 644 ms 4544 KB Output is correct
25 Correct 1209 ms 4908 KB Output is correct
26 Correct 961 ms 5076 KB Output is correct
27 Correct 924 ms 4652 KB Output is correct
28 Correct 596 ms 6796 KB Output is correct
29 Correct 1961 ms 11576 KB Output is correct
30 Correct 4057 ms 5952 KB Output is correct
31 Correct 3542 ms 5220 KB Output is correct
32 Correct 1513 ms 2988 KB Output is correct
33 Correct 1896 ms 2952 KB Output is correct
34 Correct 1330 ms 7764 KB Output is correct
35 Correct 714 ms 5968 KB Output is correct
36 Correct 1386 ms 8164 KB Output is correct
37 Correct 1076 ms 8472 KB Output is correct
38 Correct 1039 ms 7920 KB Output is correct
39 Correct 800 ms 10856 KB Output is correct
40 Correct 3498 ms 15156 KB Output is correct
41 Correct 7299 ms 9244 KB Output is correct
42 Correct 6342 ms 7816 KB Output is correct
43 Correct 1633 ms 13092 KB Output is correct
44 Correct 3105 ms 3088 KB Output is correct
45 Correct 883 ms 7000 KB Output is correct
46 Correct 2017 ms 13560 KB Output is correct
47 Correct 2142 ms 13432 KB Output is correct
48 Correct 1979 ms 11896 KB Output is correct
49 Correct 1 ms 212 KB Output is correct