oj.uz

Submission #590199

# Submission time Handle Problem Language Result Execution time Memory
590199 2022-07-05T16:19:53 Z piOOE The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1224 ms 33440 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxN = 100000, maxU = 200000, INF = 1000000000, BL = 70;

int a[maxU], b[maxU], h[maxN], n, u;

bool cmp(int i, int j) {
    return (h[i] != h[j] ? h[i] < h[j] : i < j);
}

vector<int> mrg(vector<int>& A, vector<int>& B) {
    vector<int> C(A.size() + B.size()), ans;
    merge(A.begin(), A.end(), B.begin(), B.end(), C.begin(), cmp);
    for (int i = 0; i < C.size();) {
        int j = i;
        while (j < C.size() && C[j] == C[i]) {
            j += 1;
        }
        if ((j - i) & 1) {
            ans.push_back(C[i]);
        }
        i = j;
    }
    return ans;
}

vector<vector<int>> g[maxN];

vector<int> temp[maxN];

vector<int> ti[maxN];
vector<pair<int, int>> c[maxN];

void init(int N, int D, int H[]) {
    n = N;
    memcpy(h, H, sizeof(h[0]) * n);
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    vector<int> empt;
    memcpy(a, A, sizeof(a[0]) * u), memcpy(b, B, sizeof(b[0]) * u);
    set<pair<int, int>> adj;
    for (int i = 0; i < u; ++i) {
        if (a[i] > b[i]) {
            swap(a[i], b[i]);
        }
        auto upd = [&](int x, int y) {
            temp[x].push_back(y);
            c[x].emplace_back(y, i + 1);
            if (c[x].size() % BL == 0) {
                sort(temp[x].begin(), temp[x].end(), cmp);
                g[x].push_back(mrg(g[x].empty() ? empt : g[x].back(), temp[x]));
                ti[x].push_back(i + 1);
                temp[x].clear();
            }
        };
        upd(a[i], b[i]), upd(b[i], a[i]);
        if (adj.count({a[i], b[i]})) {
            adj.erase({a[i], b[i]});
        } else {
            adj.insert({a[i], b[i]});
        }
    }
}

vector<int> get(int x, int v) {
    int it = upper_bound(ti[x].begin(), ti[x].end(), v) - ti[x].begin() - 1, t = 0;
    vector<int> ans;
    if (it > -1) {
        ans = g[x][it];
        t = ti[x][it] + 1;
    }
    it = lower_bound(c[x].begin(), c[x].end(), make_pair(-1, t), [](pair<int, int> a, pair<int, int> b) {
        return a.second < b.second;
    }) - c[x].begin();
    vector<int> nw;
    for (; it < int(c[x].size()) && c[x][it].second <= v; ++it) {
        auto [y, tt] = c[x][it];
        nw.push_back(y);
    }
    sort(nw.begin(), nw.end(), cmp);
    return mrg(ans, nw);
}

int question(int x, int y, int v) {
    int ans = INF;
    vector<int> f = get(x, v), s = get(y, v);
    int pnt = 0;
    for (int to: f) {
        while (pnt < s.size() && h[s[pnt]] < h[to]) {
            pnt += 1;
        }
        if (pnt < s.size()) {
            ans = min(ans, h[s[pnt]] - h[to]);
        }
        if (pnt > 0) {
            ans = min(ans, h[to] - h[s[pnt - 1]]);
        }
    }
    return ans;
}

Compilation message

potion.cpp: In function 'std::vector<int> mrg(std::vector<int>&, std::vector<int>&)':
potion.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < C.size();) {
      |                     ~~^~~~~~~~~~
potion.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while (j < C.size() && C[j] == C[i]) {
      |                ~~^~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while (pnt < s.size() && h[s[pnt]] < h[to]) {
      |                ~~~~^~~~~~~~~~
potion.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if (pnt < s.size()) {
      |             ~~~~^~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9808 KB Output is correct
2 Correct 6 ms 9808 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 20 ms 10636 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 33404 KB Output is correct
2 Correct 426 ms 33440 KB Output is correct
3 Correct 362 ms 17768 KB Output is correct
4 Correct 816 ms 26440 KB Output is correct
5 Correct 489 ms 30032 KB Output is correct
6 Correct 1224 ms 29308 KB Output is correct
7 Correct 788 ms 25708 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 33328 KB Output is correct
2 Correct 751 ms 24892 KB Output is correct
3 Correct 744 ms 27024 KB Output is correct
4 Correct 894 ms 29328 KB Output is correct
5 Correct 518 ms 33428 KB Output is correct
6 Correct 895 ms 29428 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 11020 KB Output is correct
2 Correct 159 ms 10320 KB Output is correct
3 Correct 291 ms 10300 KB Output is correct
4 Correct 424 ms 10824 KB Output is correct
5 Correct 408 ms 11016 KB Output is correct
6 Correct 123 ms 10704 KB Output is correct
7 Correct 431 ms 10424 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 6 ms 9808 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 6 ms 9808 KB Output is correct
5 Correct 20 ms 10636 KB Output is correct
6 Correct 413 ms 33404 KB Output is correct
7 Correct 426 ms 33440 KB Output is correct
8 Correct 362 ms 17768 KB Output is correct
9 Correct 816 ms 26440 KB Output is correct
10 Correct 489 ms 30032 KB Output is correct
11 Correct 1224 ms 29308 KB Output is correct
12 Correct 788 ms 25708 KB Output is correct
13 Correct 403 ms 33328 KB Output is correct
14 Correct 751 ms 24892 KB Output is correct
15 Correct 744 ms 27024 KB Output is correct
16 Correct 894 ms 29328 KB Output is correct
17 Correct 518 ms 33428 KB Output is correct
18 Correct 895 ms 29428 KB Output is correct
19 Correct 54 ms 11020 KB Output is correct
20 Correct 159 ms 10320 KB Output is correct
21 Correct 291 ms 10300 KB Output is correct
22 Correct 424 ms 10824 KB Output is correct
23 Correct 408 ms 11016 KB Output is correct
24 Correct 123 ms 10704 KB Output is correct
25 Correct 431 ms 10424 KB Output is correct
26 Correct 554 ms 22216 KB Output is correct
27 Correct 850 ms 27132 KB Output is correct
28 Correct 838 ms 31980 KB Output is correct
29 Correct 811 ms 26476 KB Output is correct
30 Correct 1203 ms 29384 KB Output is correct
31 Correct 935 ms 25068 KB Output is correct
32 Correct 1112 ms 29320 KB Output is correct