oj.uz

Submission #681100

# Submission time Handle Problem Language Result Execution time Memory
681100 2023-01-12T10:58:03 Z nutella Game (IOI13_game) C++17
100 / 100
 12547 ms 23024 KB 
#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++;
}

int pa[30];

void st_update(int v, int i, ll k, int l, int r) {
    int kek = 0;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        pa[kek++] = v;
        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);
    for (int x = kek - 1; x >= 0; --x) {
        v = pa[x];
        d[v] = gcd(d[left[v]], d[right[v]]);
    }
}

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) / 2;

        ll ans = 0;

        if (left[v]) {
            ans = gcd(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 = 200;

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

vector<pair<int, int>> l, r;
vector<int> root;

void rebuild() {
    counter = 1;

    l.clear(), r.clear(), root.clear();

    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.push_back(xx);
            r.push_back(xx);
            root.push_back(st_create());
        } else {
            r.back() = xx;
        }
        last_sz += 1;

        st_update(root.back(), y, k, 0, C);
    }
}

int last_rebuild = 0;

void insert(pair<int, int> xx, ll k) {
    mp[xx] = k;

    ++last_rebuild;

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

    int i = -1;
    if (xx >= r.back()) {
        i = int(r.size()) - 1;
    } else if (xx <= l.front()) {
        i = 0;
    } else {
        for (int j = int(l.size()) - 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);

    clear(root[i]);
    auto it = mp.lower_bound(l[i]);
    while (it != mp.end() && it->first <= r[i]) {
        st_update(root[i], it->first.second, it->second, 0, C);
        it = next(it);
    }
}

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

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

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

ll calculate(int P, int Q, int U, int V) {
    int fi = -1, se = -1;
    ll cd = 0;
    pair<int, int> min_done = {U, V + 1};
    pair<int, int> max_done = {P, Q - 1};
    for (int i = 0; i < root.size(); ++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]);
        }
    }
    auto it = mp.upper_bound(max_done);
    for (; it != mp.end() && it->first.first <= U; it = next(it)) {
        if (it->first.second >= Q && it->first.second <= V) {
            cd = gcd(cd, it->second);
        }
    }

    it = mp.lower_bound(min_done);
    for (; it != mp.begin() && prev(it)->first.first >= P; ) {
        it = prev(it);
        if (it->first.second >= Q && it->first.second <= V) {
            cd = gcd(cd, it->second);
        }
    }

    return cd;
}

Compilation message

game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:185:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for (int i = 0; i < root.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
game.cpp:181:9: warning: unused variable 'fi' [-Wunused-variable]
  181 |     int fi = -1, se = -1;
      |         ^~
game.cpp:181:18: warning: unused variable 'se' [-Wunused-variable]
  181 |     int fi = -1, se = -1;
      |                  ^~

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 212 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 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 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 1 ms 308 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 312 KB Output is correct
4 Correct 2435 ms 7916 KB Output is correct
5 Correct 2110 ms 7368 KB Output is correct
6 Correct 2305 ms 4136 KB Output is correct
7 Correct 2317 ms 3796 KB Output is correct
8 Correct 1348 ms 2892 KB Output is correct
9 Correct 2216 ms 3020 KB Output is correct
10 Correct 2294 ms 2712 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 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 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2395 ms 5564 KB Output is correct
13 Correct 3304 ms 1736 KB Output is correct
14 Correct 973 ms 836 KB Output is correct
15 Correct 3467 ms 2092 KB Output is correct
16 Correct 1031 ms 2480 KB Output is correct
17 Correct 1845 ms 2264 KB Output is correct
18 Correct 3245 ms 2968 KB Output is correct
19 Correct 2817 ms 3688 KB Output is correct
20 Correct 2633 ms 3168 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 312 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 312 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 212 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 2485 ms 7920 KB Output is correct
13 Correct 2060 ms 7552 KB Output is correct
14 Correct 2366 ms 4164 KB Output is correct
15 Correct 2329 ms 3804 KB Output is correct
16 Correct 1445 ms 3704 KB Output is correct
17 Correct 2295 ms 3956 KB Output is correct
18 Correct 2530 ms 3528 KB Output is correct
19 Correct 2546 ms 6544 KB Output is correct
20 Correct 3343 ms 2716 KB Output is correct
21 Correct 955 ms 1740 KB Output is correct
22 Correct 3619 ms 2844 KB Output is correct
23 Correct 1037 ms 3192 KB Output is correct
24 Correct 1912 ms 3088 KB Output is correct
25 Correct 3272 ms 3592 KB Output is correct
26 Correct 2915 ms 3208 KB Output is correct
27 Correct 2682 ms 2188 KB Output is correct
28 Correct 2302 ms 4260 KB Output is correct
29 Correct 3848 ms 8224 KB Output is correct
30 Correct 5725 ms 3468 KB Output is correct
31 Correct 4727 ms 2908 KB Output is correct
32 Correct 1266 ms 780 KB Output is correct
33 Correct 1612 ms 900 KB Output is correct
34 Correct 1959 ms 5328 KB Output is correct
35 Correct 2407 ms 3688 KB Output is correct
36 Correct 4560 ms 5628 KB Output is correct
37 Correct 4026 ms 5752 KB Output is correct
38 Correct 3857 ms 5244 KB Output is correct
39 Correct 3272 ms 4872 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 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 2424 ms 6100 KB Output is correct
13 Correct 2087 ms 6400 KB Output is correct
14 Correct 2392 ms 3228 KB Output is correct
15 Correct 2262 ms 2928 KB Output is correct
16 Correct 1531 ms 3088 KB Output is correct
17 Correct 2407 ms 3052 KB Output is correct
18 Correct 2305 ms 2660 KB Output is correct
19 Correct 2496 ms 5536 KB Output is correct
20 Correct 3490 ms 1824 KB Output is correct
21 Correct 1107 ms 968 KB Output is correct
22 Correct 3443 ms 1844 KB Output is correct
23 Correct 1033 ms 2332 KB Output is correct
24 Correct 2041 ms 2232 KB Output is correct
25 Correct 3395 ms 2748 KB Output is correct
26 Correct 2857 ms 2832 KB Output is correct
27 Correct 2680 ms 2236 KB Output is correct
28 Correct 2443 ms 4256 KB Output is correct
29 Correct 3939 ms 8256 KB Output is correct
30 Correct 5703 ms 3548 KB Output is correct
31 Correct 5416 ms 2944 KB Output is correct
32 Correct 1357 ms 820 KB Output is correct
33 Correct 1748 ms 840 KB Output is correct
34 Correct 2029 ms 5264 KB Output is correct
35 Correct 2354 ms 3748 KB Output is correct
36 Correct 4409 ms 5548 KB Output is correct
37 Correct 4035 ms 6028 KB Output is correct
38 Correct 3831 ms 6160 KB Output is correct
39 Correct 4548 ms 18512 KB Output is correct
40 Correct 8882 ms 23024 KB Output is correct
41 Correct 12547 ms 14080 KB Output is correct
42 Correct 10379 ms 12464 KB Output is correct
43 Correct 5472 ms 17780 KB Output is correct
44 Correct 1921 ms 10452 KB Output is correct
45 Correct 3417 ms 15060 KB Output is correct
46 Correct 9035 ms 21768 KB Output is correct
47 Correct 9087 ms 21792 KB Output is correct
48 Correct 8367 ms 21392 KB Output is correct
49 Correct 0 ms 212 KB Output is correct