제출 #1230998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230998		The_Samurai	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	1599 ms	74360 KiB

potion

#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9;

int n, sz;
vector<int> h;
vector<vector<pair<int, int>>> have;

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

void curseChanges(int m, int A[], int B[]) {
    sz = 1;
    while (sz <= m) sz *= 2;
    have.assign(2 * sz, vector(0, make_pair(0, 0)));
    auto add = [&](int l, int r, int a, int b) -> void {
        // cout << l << ' ' << r << ' ' << a << ' ' << b << endl;
        for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                have[l].emplace_back(a, h[b]);
                have[l].emplace_back(b, h[a]);
                l++;
            }
            if (r & 1) {
                r--;
                have[r].emplace_back(a, h[b]);
                have[r].emplace_back(b, h[a]);
            }
        }
    };
    map<pair<int, int>, int> mp;
    for (int i = 0; i < m; i++) {
        if (A[i] > B[i]) swap(A[i], B[i]);
        if (mp[{A[i], B[i]}] > 0) {
            add(mp[{A[i], B[i]}], i, A[i], B[i]);
            mp[{A[i], B[i]}] = 0;
        } else {
            mp[{A[i], B[i]}] = i + 1;
        }
    }
    for (auto it: mp) {
        if (it.second > 0) add(it.second, m, it.first.first, it.first.second);
    }
    for (int i = 1; i < have.size(); i++) sort(have[i].begin(), have[i].end());
}

int question(int x, int y, int p) {
    vector<int> vec1, vec2;
    for (p += sz; p > 0; p >>= 1) {
        int i = lower_bound(have[p].begin(), have[p].end(), make_pair(x, 0)) - have[p].begin();
        while (i < have[p].size() and have[p][i].first == x) {
            vec1.emplace_back(have[p][i++].second);
        }
        i = lower_bound(have[p].begin(), have[p].end(), make_pair(y, 0)) - have[p].begin();
        while (i < have[p].size() and have[p][i].first == y) {
            vec2.emplace_back(have[p][i++].second);
        }
    }
    if (vec1.empty() or vec2.empty()) return inf;
    sort(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());
    // cout << vec1.size() << ' ' << vec2.size() << endl;
    // for (int x: vec1) cout << x << ' ';
    // cout << endl;
    // for (int x: vec2) cout << x << ' ';
    // cout << endl;
    int ans = inf;
    int last = -2 * inf, wh = -1, i = 0, j = 0;
    while (i < vec1.size() or j < vec2.size()) {
        if (j < vec2.size() and (i == vec1.size() or vec1[i] > vec2[j])) {
            if (wh == 1) ans = min(ans, vec2[j] - last);
            wh = 2;
            last = vec2[j];
            j++;
        } else {
            if (wh == 2) ans = min(ans, vec1[i] - last);
            wh = 1;
            last = vec1[i];
            i++;
        }
    }
    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