oj.uz

Submission #590200

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

using namespace std;

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

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 7 ms 9808 KB Output is correct
2 Correct 7 ms 9808 KB Output is correct
3 Correct 7 ms 9808 KB Output is correct
4 Correct 18 ms 10660 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 33472 KB Output is correct
2 Correct 461 ms 33400 KB Output is correct
3 Correct 376 ms 17884 KB Output is correct
4 Correct 785 ms 27424 KB Output is correct
5 Correct 563 ms 30108 KB Output is correct
6 Correct 1277 ms 30784 KB Output is correct
7 Correct 666 ms 25764 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 33440 KB Output is correct
2 Correct 723 ms 26160 KB Output is correct
3 Correct 772 ms 27624 KB Output is correct
4 Correct 933 ms 30740 KB Output is correct
5 Correct 515 ms 33508 KB Output is correct
6 Correct 941 ms 30748 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11028 KB Output is correct
2 Correct 149 ms 10232 KB Output is correct
3 Correct 250 ms 10192 KB Output is correct
4 Correct 367 ms 10800 KB Output is correct
5 Correct 339 ms 11072 KB Output is correct
6 Correct 121 ms 10704 KB Output is correct
7 Correct 370 ms 10456 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 7 ms 9808 KB Output is correct
3 Correct 7 ms 9808 KB Output is correct
4 Correct 7 ms 9808 KB Output is correct
5 Correct 18 ms 10660 KB Output is correct
6 Correct 445 ms 33472 KB Output is correct
7 Correct 461 ms 33400 KB Output is correct
8 Correct 376 ms 17884 KB Output is correct
9 Correct 785 ms 27424 KB Output is correct
10 Correct 563 ms 30108 KB Output is correct
11 Correct 1277 ms 30784 KB Output is correct
12 Correct 666 ms 25764 KB Output is correct
13 Correct 449 ms 33440 KB Output is correct
14 Correct 723 ms 26160 KB Output is correct
15 Correct 772 ms 27624 KB Output is correct
16 Correct 933 ms 30740 KB Output is correct
17 Correct 515 ms 33508 KB Output is correct
18 Correct 941 ms 30748 KB Output is correct
19 Correct 63 ms 11028 KB Output is correct
20 Correct 149 ms 10232 KB Output is correct
21 Correct 250 ms 10192 KB Output is correct
22 Correct 367 ms 10800 KB Output is correct
23 Correct 339 ms 11072 KB Output is correct
24 Correct 121 ms 10704 KB Output is correct
25 Correct 370 ms 10456 KB Output is correct
26 Correct 489 ms 22724 KB Output is correct
27 Correct 818 ms 27760 KB Output is correct
28 Correct 831 ms 32660 KB Output is correct
29 Correct 701 ms 27472 KB Output is correct
30 Correct 1078 ms 30844 KB Output is correct
31 Correct 942 ms 26392 KB Output is correct
32 Correct 1113 ms 30692 KB Output is correct