Submission #702367

#	Time	Username	Problem	Language	Result	Execution time	Memory
702367		Cyanmond	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	741 ms	148168 KiB

potion

#include <bits/stdc++.h>
 
using i64 = long long;
int n, u;
std::vector<int> h;
std::vector<int> a, b;
 
constexpr int inf = 1000000000;
std::array<std::vector<std::pair<int, bool>>, 100000> sMemo;
int memoIdx = 1;
std::vector<std::vector<int>> events, memoList;
constexpr int BS = 5;
 
void init(int N, int d, int H[]) {
    n = N; 
    events.resize(n);
    memoList.resize(n);
    for (int i = 0; i < n; ++i) {
        h.push_back(H[i]);
    }
}
 
bool comp(std::pair<int, bool> a, std::pair<int, bool> b) {
    int x = h[a.first], y = h[b.first];
    if (x == y) {
        return a.first < b.first;
    } else {
        return x < y;
    }
}
 
void curseChanges(int U, int A[], int B[]) {
    u = U;
    for (int i = 0; i < u; ++i) {
        a.push_back(A[i]);
        b.push_back(B[i]);
        events[a[i]].push_back(i);
        events[b[i]].push_back(i);
    }
    for (int x = 0; x < n; ++x) {
        memoList[x].push_back(0);
        std::vector<std::pair<int, bool>> trustList;
        for (int i = 0; i < (int)events[x].size(); ++i) {
            const int j = events[x][i];
            const int v = a[j] xor b[j] xor x;
            auto itr = std::lower_bound(trustList.begin(), trustList.end(), std::make_pair(v, false), comp);
            if (itr == trustList.end() or *itr != std::make_pair(v, true)) {
                trustList.insert(itr, std::make_pair(v, true));
            } else {
                trustList.erase(itr);
            }
            if (i % BS == BS - 1) {
                memoList[x].push_back(memoIdx);
                sMemo[memoIdx++] = trustList;
            }
        }
    }
}
 
int question(int x, int y, int v) {
    // check
    
    auto itr = std::lower_bound(events[x].begin(), events[x].end(), v);
    const int r1 = itr - events[x].begin();
    itr = std::lower_bound(events[y].begin(), events[y].end(), v);
    const int r2 = itr - events[y].begin();
    
    auto &vec1 = sMemo[memoList[x][r1 / BS]];
    auto &vec2 = sMemo[memoList[y][r2 / BS]];
 
    std::vector<int> extraQ1, extraQ2;
    for (int i = r1 / BS * BS; i < r1; ++i) {
        const int j = events[x][i];
        const int v = a[j] xor b[j] xor x;
        extraQ1.push_back(v);
    }
    for (int i = r2 / BS * BS; i < r2; ++i) {
        const int j = events[y][i];
        const int v = a[j] xor b[j] xor y;
        extraQ2.push_back(v);
    }
    const int c = (int)extraQ1.size(), d = (int)extraQ2.size();
    std::unordered_map<int, bool> isOn1(c), isOn2(d);
    for (int i = 0; i < c; ++i) {
        auto itr = std::lower_bound(vec1.begin(), vec1.end(), std::make_pair(extraQ1[i], false), comp);
        if (itr == vec1.end() or itr->first != extraQ1[i]) {
            isOn1[extraQ1[i]] = false;
        } else {
            isOn1[extraQ1[i]] = true;
        }
    }
    for (int i = 0; i < d; ++i) {
        auto itr = std::lower_bound(vec2.begin(), vec2.end(), std::make_pair(extraQ2[i], false), comp);
        if (itr == vec2.end() or itr->first != extraQ2[i]) {
            isOn2[extraQ2[i]] = false;
        } else {
            isOn2[extraQ2[i]] = true;
        }
    }
    
    for (int i = 0; i < c; ++i) {
        isOn1[extraQ1[i]] = not isOn1[extraQ1[i]];
    }
    for (int i = 0; i < d; ++i) {
        isOn2[extraQ2[i]] = not isOn2[extraQ2[i]];
    }
    for (const auto &[v, sta] : isOn1) {
        if (sta) {
            continue;
        }
        auto itr = std::lower_bound(vec1.begin(), vec1.end(), std::make_pair(v, false), comp);
        if (itr == vec1.end() or itr->first != v) {
            continue;
        }
        itr->second = false;
    }
    for (const auto &[v, sta] : isOn2) {
        if (sta) {
            continue;
        }
        auto itr = std::lower_bound(vec2.begin(), vec2.end(), std::make_pair(v, false), comp);
        if (itr == vec2.end() or itr->first != v) {
            continue;
        }
        itr->second = false;
    }
 
    int answer = inf;
    int j = 0;
    for (int i = 0; i < (int)vec1.size(); ++i) {
        if (not vec1[i].second) {
            continue;
        }
        while (j != (int)vec2.size() and (h[vec1[i].first] > h[vec2[j].first] or (not vec2[j].second))) {
            if (j != (int)vec2.size() and vec2[j].second) {
                answer = std::min(answer, std::abs(h[vec2[j].first] - h[vec1[i].first]));
            }
            if ((not vec2.empty()) and j != 0 and vec2[j - 1].second) {
                answer = std::min(answer, std::abs(h[vec1[i].first] - h[vec2[j - 1].first]));
            }
            ++j;
        }
        if (j != (int)vec2.size() and vec2[j].second) {
            answer = std::min(answer, h[vec2[j].first] - h[vec1[i].first]);
        }
        if ((not vec2.empty()) and j != 0 and vec2[j - 1].second) {
            answer = std::min(answer, h[vec1[i].first] - h[vec2[j - 1].first]);
        }
    }
 
    for (const auto &[v, sta] : isOn1) {
        if (not sta) {
            continue;
        }
        auto itr = std::lower_bound(vec2.begin(), vec2.end(), std::make_pair(v, false), comp);
        while (itr != vec2.end() and (not itr->second)) {
            ++itr;
        }
        if (itr != vec2.end()) {
            answer = std::min(answer, std::abs(h[itr->first] - h[v]));
        }
        if (itr == vec2.end()) {
            if (itr == vec2.begin()) {
                continue;
            }
        }
        if (itr != vec2.begin()) {
            --itr;
        }
        while (itr != vec2.begin() and (not itr->second)) {
            --itr;
        }
        if ((not vec2.empty()) and itr->second) {
            answer = std::min(answer, std::abs(h[v] - h[itr->first]));
        }
    }
    for (const auto &[v, sta] : isOn2) {
        if (not sta) {
            continue;
        }
        auto itr = std::lower_bound(vec1.begin(), vec1.end(), std::make_pair(v, false), comp);
        while (itr != vec1.end() and (not itr->second)) {
            ++itr;
        }
        if (itr != vec1.end()) {
            answer = std::min(answer, std::abs(h[itr->first] - h[v]));
        }
        if (itr == vec1.end()) {
            if (itr == vec1.begin()) {
                continue;
            }
        }
        if (itr != vec1.begin()) {
            --itr;
        }
        while (itr != vec1.begin() and (not itr->second)) {
            --itr;
        }
        if ((not vec1.empty()) and itr->second) {
            answer = std::min(answer, std::abs(h[v] - h[itr->first]));
        }
    }
    for (const auto &[v, sta] : isOn1) {
        if (not sta) {
            continue;
        }
        for (const auto &[v2, sta2] : isOn2) {
            if (not sta2) {
                continue;
            }
            answer = std::min(answer, std::abs(h[v] - h[v2]));
        }
    }
 
    for (const auto &[v, sta] : isOn1) {
        if (sta) {
            continue;
        }
        auto itr = std::lower_bound(vec1.begin(), vec1.end(), std::make_pair(v, false), comp);
        if (itr == vec1.end() or itr->first != v) {
            continue;
        }
        itr->second = true;
    }
    for (const auto &[v, sta] : isOn2) {
        if (sta) {
            continue;
        }
        auto itr = std::lower_bound(vec2.begin(), vec2.end(), std::make_pair(v, false), comp);
        if (itr == vec2.end() or itr->first != v) {
            continue;
        }
        itr->second = true;
    }
    return answer;
}

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