Submission #1275188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275188		AksLolCoding	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2651 ms	123876 KiB

potion

#include <bits/stdc++.h>
using namespace std;

const int c = 50;
int n, d, u;
vector<int> h;

struct cmp {
    bool operator()(int x, int y) const {
        if (h[x] == h[y]) return x < y;
        return h[x] < h[y];
    }
};

using cset = set<int, cmp>;

vector<map<int, int>> upds;
vector<map<int, cset>> cache;
vector<cset> adj;
vector<int> ucnt;

void init(int N, int D, int H[]) {
    n = N, d = D;
    h.insert(h.end(), H, H+n);
}

void toggle(cset &s, int x) {
    auto ins = s.insert(x);
    if (ins.second == false) {
        s.erase(ins.first);
    }
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    upds.resize(n);
    adj.resize(n);
    ucnt.resize(n);
    cache.assign(n, {{0, {}}});
    for (int i = 1; i <= u; i++) {
        int a = A[i-1], b = B[i-1];
        for (int _ = 0; _ < 2; _++) {
            upds[a][i] = b;
            toggle(adj[a], b);
            if ((++ucnt[a]) % c == 0) {
                cache[a][i] = adj[a];
            };
            swap(a, b);
        }
    }
}

cset getadj(int x, int v) {
    // perform all updates at times <= v
    auto it1 = --cache[x].upper_bound(v);
    int t = it1->first;
    cset s = it1->second;
    auto it2 = upds[x].upper_bound(t);
    while (it2 != upds[x].end() && it2->first <= v) {
        toggle(s, it2->second);
        it2++;
    }
    return s;
}

int question(int x, int y, int v) {
    auto sx = getadj(x, v), sy = getadj(y, v);
    int ans = 1e9;
    auto itx = sx.begin(), ity = sy.begin();
    while (itx != sx.end() && ity != sy.end()) {
        ans = min(ans, abs(h[*itx] - h[*ity]));
        if (h[*itx] < h[*ity]) ++itx;
        else ++ity;
    }
    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