Submission #1140163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140163		anmattroi	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	587 ms	193724 KiB

potion

/**
Task: CEOI 2020_POTION
Link: https://oj.uz/problem/view/CEOI20_potion
**/
#include <bits/stdc++.h>
#define maxn 100005
#define maxu 200005
#define maxd 505
#define maxq 50005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, d, u;
int h[maxn], a[maxu], b[maxu];

vector<int> rem[maxn];
vector<int> days[maxn];
int cnt[maxn];


struct persistent_it {
    vector<int> it, L, R, root;
    int nt = 0;

    int build(int lo, int hi) {
        if (lo == hi) return ++nt;
        int cur = ++nt, mid = (lo + hi) >> 1;
        L[cur] = build(lo, mid);
        R[cur] = build(mid+1, hi);
        return cur;
    }

     void init(int n, int d) {
        it.resize(2*n + 20*d + 5, 0);
        L.resize(2*n + 20*d + 5, 0);
        R.resize(2*n + 20*d + 5, 0);
        root.resize(d + 1, 0);
        root[0] = build(1, n);
    }



    int upd(int u, int oldver, int lo, int hi) {
        if (lo == hi) {
            it[++nt] = 1 - it[oldver];
            assert(nt < it.size());
            return nt;
        }
        int cur = ++nt, mid = (lo + hi) >> 1;
        assert(cur < it.size());
        if (u <= mid) {
            L[cur] = upd(u, L[oldver], lo, mid);
            R[cur] = R[oldver];
        } else {
            L[cur] = L[oldver];
            R[cur] = upd(u, R[oldver], mid+1, hi);
        }
        it[cur] = it[L[cur]] + it[R[cur]];
        return cur;
    }


    void get(int r, vector<int> &cr, int lo, int hi) {
        if (lo == hi) {
            if (it[r]) cr.emplace_back(lo);
            return;
        }
        int mid = (lo + hi) >> 1;
        if (it[L[r]]) get(L[r], cr, lo, mid);
        if (it[R[r]]) get(R[r], cr, mid+1, hi);
    }

} tree[maxn];


void precompute() {
    map<ii, int> nho;
    for (int i = 1; i <= n; i++) rem[i].resize(1, 0);
    for (int i = 1; i <= n; i++) days[i].resize(1, 0);

    for (int i = 1; i <= u; i++) {
        if (a[i] > b[i]) swap(a[i], b[i]);
        days[a[i]].emplace_back(i);
        days[b[i]].emplace_back(i);
        if (nho.count({a[i], b[i]})) continue;
        nho[{a[i], b[i]}] = 1;
        rem[a[i]].emplace_back(b[i]);
        rem[b[i]].emplace_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (rem[i].size() > 1) {
            sort(rem[i].begin() + 1, rem[i].end(), [&](int x, int y) {return h[x] < h[y];});
            for (int o = 1; o < rem[i].size(); o++) nho[{i, rem[i][o]}] = o;
            tree[i].init(rem[i].size()-1, days[i].size());
        }
    }

    for (int o = 1; o <= u; o++) {
        int u = a[o], v = b[o];
        int p1 = nho[{u, v}], p2 = nho[{v, u}];
        assert(p1 && p2);
        ++cnt[u]; ++cnt[v];
        tree[u].root[cnt[u]] = tree[u].upd(p1, tree[u].root[cnt[u]-1], 1, rem[u].size()-1);
        tree[v].root[cnt[v]] = tree[v].upd(p2, tree[v].root[cnt[v]-1], 1, rem[v].size()-1);
    }
}

void init(int N, int D, int H[]) {
    n = N; d = D;
    for (int i = 1; i <= n; i++) h[i] = H[i-1];
}

void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 1; i <= u; i++) {
        a[i] = A[i-1]+1;
        b[i] = B[i-1]+1;
    }
    precompute();
}

int question(int x, int y, int v) {
    ++x; ++y;
    int ans = 1000000000;
    if (days[x].size() == 1 || days[y].size() == 1) return ans;
    int D1 = upper_bound(days[x].begin(), days[x].end(), v) - days[x].begin() - 1;
    int D2 = upper_bound(days[y].begin(), days[y].end(), v) - days[y].begin() - 1;

    vector<int> a, b;


    tree[x].get(tree[x].root[D1], a, 1, rem[x].size()-1);
    tree[y].get(tree[y].root[D2], b, 1, rem[y].size()-1);

    if (a.empty() || b.empty()) return ans;

    for (int i = 0; i < a.size(); i++) a[i] = h[rem[x][a[i]]];
    for (int i = 0; i < b.size(); i++) b[i] = h[rem[y][b[i]]];

    for (int l = 0, r = 0; l < a.size(); l++) {
        while (r < b.size() && b[r] < a[l]) ++r;
        ans = min(ans, abs(a[l]-b[r]));
        if (r > 0) ans = min(ans, abs(a[l]-b[r-1]));
    }

    return ans;
}

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