Submission #1186275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186275		Unforgettablepl	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	3078 ms	98360 KiB

potion

#include <bits/stdc++.h>
using namespace std;


namespace {
    const int threshold = 50; // Can change
    vector<vector<pair<int,int>>> updates;
    vector<vector<pair<int,set<int>>>> blocks;
    vector<int> h;
    int N;
}

void init(int N, int D, int H[]) {
    updates.resize(N);
    ::N = N;
    blocks.resize(N);
    h.resize(N);
    for(int i=0;i<N;i++){
        h[i]=H[i];
        blocks[i].emplace_back(0,set<int>());
    }
}

void curseChanges(int U, int A[], int B[]) {
    vector<set<int>> curr(N);
    vector<int> currUpdates(N);
    for(int i=0;i<U;i++){
        // Process A->B
        int upd = B[i];
        if(curr[A[i]].count(B[i])){
            upd=-upd-1;curr[A[i]].erase(B[i]);
        } else {
            curr[A[i]].insert(B[i]);
        }
        updates[A[i]].emplace_back(i+1,upd);
        if(++currUpdates[A[i]] == threshold){
            currUpdates[A[i]]=0;
            blocks[A[i]].emplace_back(i+1,curr[A[i]]);
        }
        // Process B->A
        upd = A[i];
        if(curr[B[i]].count(A[i])){
            upd=-upd-1;curr[B[i]].erase(A[i]);
        } else {
            curr[B[i]].insert(A[i]);
        }
        updates[B[i]].emplace_back(i+1,upd);
        if(++currUpdates[B[i]] == threshold){
            currUpdates[B[i]]=0;
            blocks[B[i]].emplace_back(i+1,curr[B[i]]);
        }
    }
}

int question(int x, int y, int v) {
    auto recover = [&](int curr){
        auto base = --upper_bound(blocks[curr].begin(),blocks[curr].end(),v,[](const int& a,const pair<int,set<int>>& b){return a<b.first;});
        int st = base->first;
        set<int> ans = base->second;
        auto iter = upper_bound(updates[curr].begin(),updates[curr].end(),st,[](const int& a,const pair<int,int>& b){return a<b.first;});
        while(iter!=updates[curr].end() and iter->first <=v){
            int upd = iter->second;
            if(upd<0){
                upd= -upd-1;
                ans.erase(upd);
            } else ans.insert(upd);
            iter++;
        }
        vector<int> heights;
        for(int i:ans)heights.emplace_back(h[i]);
        sort(heights.begin(),heights.end());
        return heights;
    };
    auto htX = recover(x);
    auto htY = recover(y);
    auto f = htX.begin();
    auto s = htY.begin();
    int ans = 1e9;
    while(f!=htX.end() and s!=htY.end()){
        ans = min(ans,abs((*f)-(*s)));
        if(*f < *s)f++;
        else s++;
    }
    return ans;
}

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