Submission #1195623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195623		new	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	1687 ms	55348 KiB

potion

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


namespace {
    const int threshold = 10; // Can change
    vector<vector<pair<int,int>>> updates(100000);
    vector<vector<pair<int,vector<int>>>> blocks(100000);
    vector<int> h(100000);
    int N;
}

void flip(vector<int> &a,int x){
    int ok = -1, empty=-1;
    for(int i=0;i<a.size();i++){
        if(a[i]==-1)empty=i;
        else if(a[i]==x){ok=1;a[i]=-1;break;}
    }
    if(ok==-1){
        if(empty==-1)a.emplace_back(x);
        else a[empty]=x;
    }
}

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

void curseChanges(int U, int A[], int B[]) {
    vector<vector<int>> curr(N);
    vector<int> currUpdates(N);
    for(int i=0;i<U;i++){
        // Process A->B
        flip(curr[A[i]],B[i]);
        updates[A[i]].emplace_back(i+1,B[i]);
        if(++currUpdates[A[i]] == threshold){
            currUpdates[A[i]]=0;
            blocks[A[i]].emplace_back(i+1,curr[A[i]]);
        }
        // Process B->A
        flip(curr[B[i]],A[i]);
        updates[B[i]].emplace_back(i+1,A[i]);
        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,vector<int>>& b){return a<b.first;});
        int st = base->first;
        vector<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;
            flip(ans,upd);
            iter++;
        }
        vector<int> heights;
        for(int&i:ans)if(i!=-1)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: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30