Submission #1325736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325736		shirokuma5	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	1668 ms	40708 KiB

potion

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
const int C = 50;

int n, d, u;
vector<int> h, a, b;
vector<vector<vector<int>>> lis;
vector<vector<int>> lday;
vector<vector<int>> op;
vector<bool> cnt;

void chmin(int &a, int b) {
    if (a > b) a = b;
}

void init(int N, int D, int H[]) {
    n = N; d = D;
    h.resize(N);
    rep(i, N) h[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    a.resize(U); b.resize(U);
    rep(i, U) {
        a[i] = A[i]; b[i] = B[i];
        if (a[i] > b[i]) swap(a[i], b[i]);
    }

    lis.assign(n, {{}}); lday.resize(n, {0}); op.resize(n); cnt.resize(U+1);
    set<pair<int, int>> se;
    rep(i, U) {
        op[a[i]].push_back(i+1); op[b[i]].push_back(i+1);
        if (op[a[i]].size() % C == 1) {
            lis[a[i]].push_back(lis[a[i]].back());
            lday[a[i]].push_back(i+1);
        }
        if (op[b[i]].size() % C == 1) {
            lday[b[i]].push_back(i+1); lis[b[i]].push_back(lis[b[i]].back());
        }
        cnt[i+1] = se.count({a[i], b[i]});
        if (se.count({a[i], b[i]})) {
            se.erase({a[i], b[i]});
            lis[a[i]].back().erase(find(lis[a[i]].back().begin(), lis[a[i]].back().end(), h[b[i]]));
            lis[b[i]].back().erase(find(lis[b[i]].back().begin(), lis[b[i]].back().end(), h[a[i]]));
        }
        else {
            se.insert({a[i], b[i]});
            lis[a[i]].back().push_back(h[b[i]]); lis[b[i]].back().push_back(h[a[i]]);
        }
        lday[a[i]].back() = i + 1; lday[b[i]].back() = i + 1;
    }
}

int question(int x, int y, int v) {
    int idx = distance(lday[x].begin(), upper_bound(lday[x].begin(), lday[x].end(), v))-1;
    int idy = distance(lday[y].begin(), upper_bound(lday[y].begin(), lday[y].end(), v))-1;
    auto vx = lis[x][idx], vy = lis[y][idy];
    auto it = upper_bound(op[x].begin(), op[x].end(), lday[x][idx]);
    while (it != op[x].end() && *it <= v) {
        if (cnt[*it]) vx.erase(find(vx.begin(), vx.end(), h[a[*it-1]+b[*it-1]-x]));
        else vx.push_back(h[a[*it-1]+b[*it-1]-x]);
        it++;
    }
    it = upper_bound(op[y].begin(), op[y].end(), lday[y][idy]);
    while (it != op[y].end() && *it <= v) {
        if (cnt[*it]) vy.erase(find(vy.begin(), vy.end(), h[a[*it-1]+b[*it-1]-y]));
        else vy.push_back(h[a[*it-1]+b[*it-1]-y]);
        it++;
    }
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    int res = 1e9;
    int i = 0, j = 0;
    while (i < vx.size() && j < vy.size()) {
        chmin(res, abs(vx[i] - vy[j]));
        if (vx[i] <= vy[j]) i++;
        else j++;
    }
    return res;
}

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