Submission #1228028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228028		Turkhuu	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	1651 ms	39624 KiB

potion

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int N = 1e5 + 5, C = 50;
int h[N];
bool seen[N];
set<int> cur[N];
vector<array<int, 3>> upds[N];
vector<vector<int>> adj[N];
void upd(int x, int y, int d) {
    if (cur[x].count(y)) {
        cur[x].erase(y);
        upds[x].push_back({d, y, -1});
    } else {
        cur[x].insert(y);
        upds[x].push_back({d, y, 1});
    }
    if (upds[x].size() % C == 0) {
        adj[x].push_back({});
        for (int y : cur[x])
            adj[x].back().push_back(y);
    }
}
void init(int n, int d, int _h[]) {
    copy(_h, _h + n, h);
}
void curseChanges(int U, int A[], int B[]) {
    FOR(i, 0, U - 1)
        upd(A[i], B[i], i),
        upd(B[i], A[i], i);
}
vector<int> get(int x, int d) {
    int n = lower_bound(upds[x].begin(), upds[x].end(), array<int, 3>{d, -1, -1}) - upds[x].begin();
    vector<int> ans;
    ROF(i, n - 1, n / C * C) {
        auto [_, y, z] = upds[x][i];
        if (!seen[y]) {
            seen[y] = 1;
            if (z == 1)
                ans.push_back(h[y]);
        }
    }
    if (n >= C)
        for (int y : adj[x][n / C - 1])
            if (!seen[y])
                ans.push_back(h[y]);
    FOR(i, n / C * C, n - 1) seen[upds[x][i][1]] = 0;
    return ans;
};
int question(int x, int y, int d) {
    auto hx = get(x, d);
    auto hy = get(y, d);
    sort(hx.begin(), hx.end());
    sort(hy.begin(), hy.end());
    int nx = hx.size(), ny = hy.size(), j = -1, ans = 1e9;
    FOR(i, 0, nx - 1) {
        while (j + 1 < ny && hy[j + 1] <= hx[i]) j++;
        if (j >= 0) ans = min(ans, hx[i] - hy[j]);
        if (j + 1 < ny) ans = min(ans, hy[j + 1] - hx[i]);
    }
    return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30