Submission #1230163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230163		RakhimovAmir	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	2299 ms	71360 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
vector<pair<int, int>> v[4 * N];
vector<int> A, B;
int h[N], n, U;

// void build(int x, int tl, int tr) {
//     if (tl == tr) {
//         return;
//     }
//     int tm = (tl + tr) / 2;
//     build(2 * x, tl, tm);
//     build(2 * x + 1, tm + 1, tr);
// }

void dfs(int x, int tl, int tr) {
    sort(v[x].begin(), v[x].end());
    if (tl == tr)
        return;
    int tm = (tl + tr) / 2;
    dfs(2 * x, tl, tm);
    dfs(2 * x + 1, tm + 1, tr);
}

void add(int x, int tl, int tr, int l, int r, int a, int b) {
    if (r < tl || l > tr)
        return;
    if (l <= tl && r >= tr) {
        v[x].push_back({a, b});
        v[x].push_back({b, a});
        return;
    }
    int tm = (tl + tr) / 2;
    add(2 * x, tl, tm, l, r, a, b);
    add(2 * x + 1, tm + 1, tr, l, r, a, b);
}

void go(int x, int tl, int tr, int T, int a, int b) {
    auto i = lower_bound(v[x].begin(), v[x].end(), make_pair(a, -1)) - v[x].begin();
    for (; i < v[x].size(); i++) {
        if (v[x][i].first != a)
            break;
        A.push_back(h[v[x][i].second]);
    }
    i = lower_bound(v[x].begin(), v[x].end(), make_pair(b, -1)) - v[x].begin();
    for (; i < v[x].size(); i++) {
        if (v[x][i].first != b)
            break;
        B.push_back(h[v[x][i].second]);
    }
    if (tl == tr) {
        return;
    }
    int tm = (tl + tr) / 2;
    if (T <= tm)
        go(2 * x, tl, tm, T, a, b);
    else
        go(2 * x + 1, tm + 1, tr, T, a, b);
}

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

void curseChanges(int U, int A[], int B[]) {
    map<pair<int, int>, int> open;
    ::U = U;
    // build(1, 0, U);
    for (int i = 0; i < U; i++) {
        if (A[i] > B[i])
            swap(A[i], B[i]);
        if (open[{A[i], B[i]}]) {
            add(1, 0, U, open[{A[i], B[i]}], i, A[i], B[i]);
            open[{A[i], B[i]}] = 0;
        } else {
            open[{A[i], B[i]}] = i + 1;
        }
    }
    for (auto i : open) {
        if (i.second) {
            add(1, 0, U, i.second, U, i.first.first, i.first.second);
        }
    }
    dfs(1, 0, U);
}

int question(int x, int y, int v) {
    int res = 1e9;
    go(1, 0, U, v, x, y);
    if (A.empty() || B.empty()) {
        A.clear();
        B.clear();
        return res;
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    // cou  t << "X: " << s[x].size() << " Y: " << s[y].size() << " V: " << v << "\n";
    for (auto i : A) {
        auto r = lower_bound(B.begin(), B.end(), i);
        if (r != B.end()) {
            res = min(res, abs(i - *r));
        }
        if (r != B.begin()) {
            r--;
            res = min(res, abs(i - *r));
        }
    }
    A.clear();
    B.clear();
    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