Submission #1230089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230089		Gray	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	1482 ms	327680 KiB

potion

#pragma GCC optimize("Ofast,unroll-loops")
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second

vector<int> h;
int n, mxd, d;
vector<array<int, 2>> e;
int B=500;
vector<vector<vector<int>>> tA;

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

void curseChanges(int U, int u[], int v[]) {
    vector<set<ll>> A(n); e.resize(U);
    tA.push_back(vector<vector<int>>(n));
    for (ll i=0; i<U; i++){
        e[i] = {u[i], v[i]};
        if (A[u[i]].count(v[i])){
            A[u[i]].erase(v[i]);
            A[v[i]].erase(u[i]);
        }else{
            A[u[i]].insert(v[i]);
            A[v[i]].insert(u[i]);
        }
        if ((i+1)%B==0){
            tA.push_back(vector<vector<int>>(n));
            for (ll j=0; j<n; j++){
                for (auto x:A[j]) tA.back()[j].push_back(x);
            }
        }
    }
}
vector<int> hs; set<ll> nodes;
int question(int x, int y, int v) {
    hs.clear(); nodes.clear();
    for (auto u:tA[v/B][x]) nodes.insert(u);
    for (ll i=(v/B)*B; i<v; i++){
        if (e[i][0]==x or e[i][1]==x){
            if (e[i][1]==x) swap(e[i][0], e[i][1]);
            if (nodes.count(e[i][1])) nodes.erase(e[i][1]);
            else nodes.insert(e[i][1]);
        }
    }
    for (auto u:nodes) {
        hs.push_back(h[u]);

    }
    if (hs.empty()) return 1e9;
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());

    nodes.clear();
    for (auto u:tA[v/B][y]) nodes.insert(u);
    for (ll i=(v/B)*B; i<v; i++){
        if (e[i][0]==y or e[i][1]==y){
            if (e[i][1]==y) swap(e[i][0], e[i][1]);
            if (nodes.count(e[i][1])) nodes.erase(e[i][1]);
            else nodes.insert(e[i][1]);
        }
    }

    int mn=1e9;

    for (auto u:nodes){
        ll ind = lower_bound(hs.begin(), hs.end(), h[u])-hs.begin();
        if (ind<(ll)hs.size()){
            mn=min(mn, hs[ind]-h[u]);
        }
        if (ind){
            mn=min(mn, h[u]-hs[ind-1]);
        }
    }
    return mn;
}

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