Submission #900503

#	Time	Username	Problem	Language	Result	Execution time	Memory
900503		Dec0Dedd	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	1804 ms	86432 KiB

potion

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 8e5+10;
const int INF = 1e9;

int n, d, h[N], a[N], b[N], c;
vector<pii> T[N];

void init(int _n, int _d, int _h[]) {
    n=_n, d=_d;
    for (int i=0; i<n; ++i) h[i]=_h[i];
}

void add(int v, int l, int r, int ql, int qr, int x, int y) {
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
        T[v].push_back({x, h[y]});
        T[v].push_back({y, h[x]});
        return;
    } int m=(l+r)/2;
    add(2*v, l, m, ql, qr, x, y), add(2*v+1, m+1, r, ql, qr, x, y);
}

void curseChanges(int sz, int _a[], int _b[]) {
    c=sz;

    map<pii, vector<int>> idx;
    for (int i=1; i<=c; ++i) {
        a[i]=_a[i-1], b[i]=_b[i-1];
        if (a[i] > b[i]) swap(a[i], b[i]);
        idx[{a[i], b[i]}].push_back(i);
    }

    for (auto u : idx) {
        u.second.push_back(c+1);
        int sz=u.second.size();

        // [x0, x1, ..., xn]
        for (int i=0; i+1<sz; i+=2) {
            add(1, 1, c, u.second[i], u.second[i+1]-1, u.first.first, u.first.second);
        }
    }

    for (int i=0; i<N; ++i) sort(T[i].begin(), T[i].end());
}

void dfs(int v, int l, int r, int p, int x, vector<int> *h) {
    int i=upper_bound(T[v].begin(), T[v].end(), make_pair(x, -1))-T[v].begin();
    for (int j=i; j<(int)T[v].size(); ++j) {
        if (T[v][j].first != x) break;
        h->push_back(T[v][j].second);
    }

    if (l == r) return;
    int m=(l+r)/2;
    if (p <= m) dfs(2*v, l, m, p, x, h);
    else dfs(2*v+1, m+1, r, p, x, h);
}

int fnd(vector<int> a, vector<int> b) {
    if (a.empty() || b.empty()) return INF;
    int ptr=0, ans=INF;

    for (auto u : a) {
        while (ptr < (int)b.size()) {
            if (b[ptr] <= u) ++ptr;
            else break;
        }

        ans=min(ans, abs(u-b[min((int)b.size()-1, ptr)]));
        if (ptr > 0) ans=min(ans, abs(u-b[ptr-1]));
    } return ans;
}

int question(int x, int y, int v) {
    vector<int> hx, hy;
    dfs(1, 1, c, v, x, &hx);
    dfs(1, 1, c, v, y, &hy);
    sort(hx.begin(), hx.end()), sort(hy.begin(), hy.end());
    return fnd(hx, hy);
}

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