Submission #1230078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230078		Gray	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	3013 ms	127952 KiB

potion

#include <algorithm>
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#define ll int
#define ff first
#define ss second

vector<int> h;
int n, mxd, d;
vector<vector<vector<int>>> A;
vector<vector<pair<int, int>>> add;
vector<vector<ll>> 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[]) {
    A.resize(n); tA.resize(n); d=U; add.resize(n);
    for (int i=0; i<n; i++) {
        A[i].push_back(vector<int>()); tA[i].push_back(0);
    }
    set<ll> temp; vector<int> t2;
    for (int i=0; i<U; i++){
        temp.clear();
        for (auto x:A[u[i]].back()) temp.insert(x);
        ll lim=tA[u[i]].back(), ind=add[u[i]].size()-1;
        while (ind>=0 and add[u[i]][ind].ff>=lim){
            temp.insert(add[u[i]][ind].ss); ind--;
        }
        if (temp.count(v[i])){
            // cout << u[i] << " - " << v[i] << " -> ";
            t2.clear();
            for (auto x:A[u[i]].back()){
                if (x==v[i]) continue;
                t2.push_back(x);
            }
            ind=add[u[i]].size()-1;
            while (ind>=0 and add[u[i]][ind].ff>=tA[u[i]].back()) {
                if (add[u[i]][ind].ss==v[i]) {ind--; continue;}
                t2.push_back(add[u[i]][ind].ss); ind--;
            }
            // cout << u[i] << ": ";
            // for (auto x:t2) cout << x << " ";
            // cout << "| ";
            A[u[i]].push_back(t2);
            t2.clear();
            for (auto x:A[v[i]].back()){
                if (x==u[i]) continue;
                t2.push_back(x);
            }
            ind=add[v[i]].size()-1;
            while (ind>=0 and add[v[i]][ind].ff>=tA[v[i]].back()) {
                if (add[v[i]][ind].ss==u[i]) {ind--; continue;}
                t2.push_back(add[v[i]][ind].ss); ind--;
            }
            // cout << v[i] << ": ";
            // for (auto x:t2) cout << x << " ";
            // cout << endl;
            A[v[i]].push_back(t2);
            tA[u[i]].push_back(i+1); tA[v[i]].push_back(i+1);
        }else{
            // cout << u[i] << "+" << v[i] << endl;
            add[u[i]].push_back({i, v[i]});
            add[v[i]].push_back({i, u[i]});
        }
    }
}
vector<int> hs;
int question(int x, int y, int v) {
    // cout << x << " " << y << " " << v << endl;
    ll indx = upper_bound(tA[x].begin(), tA[x].end(), v)-tA[x].begin()-1;
    hs.clear(); for (auto u:A[x][indx]){
        hs.push_back(h[u]);
        // cout << h[u] << " ";
    }
    indx=lower_bound(add[x].begin(), add[x].end(), make_pair(tA[x][indx], 0))-add[x].begin();
    for (ll i=indx; i<(ll)add[x].size() and add[x][i].ff<=v; i++){
        hs.push_back(h[add[x][i].ss]);
        // cout << add[x][i].ss << " ";
    }
    // cout << endl;
    if (hs.empty()) return 1e9;
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());

    int mn=1e9;
    int indy = upper_bound(tA[y].begin(), tA[y].end(), v)-tA[y].begin()-1;

    for (auto u:A[y][indy]){
        // cout << u << " ";
        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]);
        }
    }
    indy=lower_bound(add[y].begin(), add[y].end(), make_pair(tA[y][indy], 0))-add[y].begin();
    for (ll i=indy; i<(ll)add[y].size() and add[y][i].ff<=v; i++){
        ll u=add[y][i].ss;
        // cout << u << " ";
        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]);
        }
    }
    // cout << endl;
    return mn;
}

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