Submission #1122495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122495		boyliguanhan	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2095 ms	159504 KiB

potion

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
map<int,set<int>>checkpoints[100100];
vector<pair<int,int>> upds[100100];
set<int>stuf[100100];
int h[100100],rev[100100],cod[100100],nnn;
void init(int n,int D,int H[]){
    vector<int>v;
    for(int i=0;i<n;i++) h[i]=H[i],
        v.push_back(i),checkpoints[i][-1];
    sort(v.begin(),v.end(),[](int a,int b){return h[a]<h[b];});
    for(int i=0;i<n;i++)
        rev[cod[v[i]]=i]=v[i];
}
int question(int a,int b,int v){
    a=cod[a],b=cod[b];
    vector<int>A,B;
    auto it=--checkpoints[a].lower_bound(v);
    set<int>X;
    swap(X,it->second);
    auto it2=lower_bound(upds[a].begin(),upds[a].end(),make_pair(it->first+1,0));
    int I=it2-upds[a].begin(),begI=I;
    for(;I<upds[a].size()&&upds[a][I].first<v;I++)
        if(X.count(upds[a][I].second))
            X.erase(upds[a][I].second);
        else X.insert(upds[a][I].second);
    for(auto i:X)A.push_back(h[rev[i]]);
    while(--I>=begI)
        if(X.count(upds[a][I].second))
            X.erase(upds[a][I].second);
        else X.insert(upds[a][I].second);
    swap(X,it->second);
    it=--checkpoints[b].lower_bound(v);
    swap(X,it->second);
    it2=lower_bound(upds[b].begin(),upds[b].end(),make_pair(it->first+1,0));
    I=it2-upds[b].begin(),begI=I;
    for(;I<upds[b].size()&&upds[b][I].first<v;I++)
        if(X.count(upds[b][I].second))
            X.erase(upds[b][I].second);
        else X.insert(upds[b][I].second);
    for(auto i:X)B.push_back(h[rev[i]]);
    while(--I>=begI)
        if(X.count(upds[b][I].second))
            X.erase(upds[b][I].second);
        else X.insert(upds[b][I].second);
    swap(X,it->second);
    int l=0,r=0,res=1e9;
    while(l<A.size()&&r<B.size()){
        res=min(res,abs(A[l]-B[r]));
        if(A[l]<B[r])l++;
        else r++;
    }
    return res;
}

void curseChanges(int u,int A[],int B[]) {
    for(int i=0;i<u;i++){
        int a,b;
        a=A[i];
        b=B[i];
        a=cod[a];
        b=cod[b];
        if(stuf[a].count(b))
            stuf[a].erase(b),
            stuf[b].erase(a);
        else stuf[a].insert(b),
            stuf[b].insert(a);
        upds[a].push_back({i,b});
        upds[b].push_back({i,a});
        if(upds[a].size()%30==0)
            checkpoints[a][i]=stuf[a];
        if(upds[b].size()%30==0)
            checkpoints[b][i]=stuf[b];
    }
}

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