oj.uz

Submission #590188

# Submission time Handle Problem Language Result Execution time Memory
590188 2022-07-05T16:09:21 Z piOOE The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1818 ms 33500 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

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

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, d = D;
    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]);
        }
        temp[a[i]].push_back(b[i]);
        temp[b[i]].push_back(a[i]);
        c[a[i]].emplace_back(b[i], i + 1);
        c[b[i]].emplace_back(a[i], i + 1);
        if (adj.count({a[i], b[i]})) {
            adj.erase({a[i], b[i]});
        } else {
            adj.insert({a[i], b[i]});
        }
        if (c[a[i]].size() % BL == 0) {
            sort(temp[a[i]].begin(), temp[a[i]].end(), cmp);
            g[a[i]].push_back(mrg(g[a[i]].empty() ? empt : g[a[i]].back(), temp[a[i]]));
            ti[a[i]].push_back(i + 1);
            temp[a[i]].clear();
        }

        if (c[b[i]].size() % BL == 0) {
            sort(temp[b[i]].begin(), temp[b[i]].end(), cmp);
            g[b[i]].push_back(mrg(g[b[i]].empty() ? empt : g[b[i]].back(), temp[b[i]]));
            ti[b[i]].push_back(i + 1);
            temp[b[i]].clear();
        }
    }
}

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

Subtask #1
0.0 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9808 KB Output is correct
2 Correct 7 ms 9808 KB Output is correct
3 Correct 8 ms 9808 KB Output is correct
4 Correct 19 ms 10568 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 33500 KB Output is correct
2 Correct 427 ms 33492 KB Output is correct
3 Correct 847 ms 17644 KB Output is correct
4 Correct 1209 ms 24668 KB Output is correct
5 Correct 504 ms 29952 KB Output is correct
6 Correct 1689 ms 25588 KB Output is correct
7 Correct 1566 ms 25684 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 33468 KB Output is correct
2 Correct 1365 ms 21044 KB Output is correct
3 Correct 1273 ms 25392 KB Output is correct
4 Correct 1446 ms 25684 KB Output is correct
5 Correct 582 ms 33272 KB Output is correct
6 Correct 1593 ms 25632 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 10960 KB Output is correct
2 Correct 182 ms 10320 KB Output is correct
3 Correct 802 ms 10192 KB Output is correct
4 Correct 954 ms 10788 KB Output is correct
5 Correct 777 ms 10976 KB Output is correct
6 Correct 134 ms 10832 KB Output is correct
7 Correct 1119 ms 10376 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 7 ms 9808 KB Output is correct
3 Correct 7 ms 9808 KB Output is correct
4 Correct 8 ms 9808 KB Output is correct
5 Correct 19 ms 10568 KB Output is correct
6 Correct 454 ms 33500 KB Output is correct
7 Correct 427 ms 33492 KB Output is correct
8 Correct 847 ms 17644 KB Output is correct
9 Correct 1209 ms 24668 KB Output is correct
10 Correct 504 ms 29952 KB Output is correct
11 Correct 1689 ms 25588 KB Output is correct
12 Correct 1566 ms 25684 KB Output is correct
13 Correct 421 ms 33468 KB Output is correct
14 Correct 1365 ms 21044 KB Output is correct
15 Correct 1273 ms 25392 KB Output is correct
16 Correct 1446 ms 25684 KB Output is correct
17 Correct 582 ms 33272 KB Output is correct
18 Correct 1593 ms 25632 KB Output is correct
19 Correct 51 ms 10960 KB Output is correct
20 Correct 182 ms 10320 KB Output is correct
21 Correct 802 ms 10192 KB Output is correct
22 Correct 954 ms 10788 KB Output is correct
23 Correct 777 ms 10976 KB Output is correct
24 Correct 134 ms 10832 KB Output is correct
25 Correct 1119 ms 10376 KB Output is correct
26 Correct 1104 ms 20936 KB Output is correct
27 Correct 1397 ms 25392 KB Output is correct
28 Correct 1236 ms 30364 KB Output is correct
29 Correct 1294 ms 24668 KB Output is correct
30 Correct 1818 ms 25636 KB Output is correct
31 Correct 1612 ms 20972 KB Output is correct
32 Correct 1750 ms 25728 KB Output is correct