oj.uz

Submission #590198

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

using namespace std;

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

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 8 ms 9840 KB Output is correct
3 Correct 7 ms 9756 KB Output is correct
4 Correct 20 ms 10644 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 33332 KB Output is correct
2 Correct 400 ms 33448 KB Output is correct
3 Correct 314 ms 18016 KB Output is correct
4 Correct 686 ms 28820 KB Output is correct
5 Correct 474 ms 30560 KB Output is correct
6 Correct 1091 ms 32116 KB Output is correct
7 Correct 611 ms 25896 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 33372 KB Output is correct
2 Correct 611 ms 27636 KB Output is correct
3 Correct 647 ms 28604 KB Output is correct
4 Correct 757 ms 32132 KB Output is correct
5 Correct 521 ms 33696 KB Output is correct
6 Correct 889 ms 32272 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10964 KB Output is correct
2 Correct 156 ms 10340 KB Output is correct
3 Correct 208 ms 10268 KB Output is correct
4 Correct 346 ms 10864 KB Output is correct
5 Correct 339 ms 11040 KB Output is correct
6 Correct 110 ms 10704 KB Output is correct
7 Correct 316 ms 10596 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 8 ms 9840 KB Output is correct
4 Correct 7 ms 9756 KB Output is correct
5 Correct 20 ms 10644 KB Output is correct
6 Correct 440 ms 33332 KB Output is correct
7 Correct 400 ms 33448 KB Output is correct
8 Correct 314 ms 18016 KB Output is correct
9 Correct 686 ms 28820 KB Output is correct
10 Correct 474 ms 30560 KB Output is correct
11 Correct 1091 ms 32116 KB Output is correct
12 Correct 611 ms 25896 KB Output is correct
13 Correct 422 ms 33372 KB Output is correct
14 Correct 611 ms 27636 KB Output is correct
15 Correct 647 ms 28604 KB Output is correct
16 Correct 757 ms 32132 KB Output is correct
17 Correct 521 ms 33696 KB Output is correct
18 Correct 889 ms 32272 KB Output is correct
19 Correct 49 ms 10964 KB Output is correct
20 Correct 156 ms 10340 KB Output is correct
21 Correct 208 ms 10268 KB Output is correct
22 Correct 346 ms 10864 KB Output is correct
23 Correct 339 ms 11040 KB Output is correct
24 Correct 110 ms 10704 KB Output is correct
25 Correct 316 ms 10596 KB Output is correct
26 Correct 473 ms 23284 KB Output is correct
27 Correct 744 ms 28472 KB Output is correct
28 Correct 765 ms 33304 KB Output is correct
29 Correct 626 ms 28848 KB Output is correct
30 Correct 1051 ms 32104 KB Output is correct
31 Correct 845 ms 27720 KB Output is correct
32 Correct 938 ms 32116 KB Output is correct