Submission #1216493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216493		anonymous321	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	2373 ms	151468 KiB

potion

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

int n, d;
//vector<int> vh;
vector<int> vhs;
vector<int> vid;

vector<vector<vector<pair<int, int>>>> vnext;
vector<vector<int>> vlast;
vector<vector<int>> id;

void init(int N, int D, int H[]) {
    n = N;
    d = D;
    vhs = vector<int> (N);
    vector<pair<int, int>> vq;
    for (int i = 0; i < N; i++) {
        vhs[i] = H[i];
        vq.push_back({vhs[i], i});
    }
    sort(vhs.begin(), vhs.end());
    sort(vq.begin(), vq.end());
    vid = vector<int> (n);
    for (int i = 0; i < N; i++) {
        vid[vq[i].second] = i;
    }

    vnext = vector<vector<vector<pair<int, int>>>> (n, {{{-1, 1}}, {{-1, -1}}});
    vlast = vector<vector<int>> (n, {-1, 0});
    id = vector<vector<int>> (n, {-1, n});
}

void rem_friend (int a, int b, int i, vector<map<int, int>> &mv, vector<set<int>> &active, vector<map<int, bool>> &mstate) {
    mstate[a][b] = false;
    int m = mv[a][b];
    int l = vlast[a][m];
    int r = vnext[a][m].back().second;
    vnext[a][l].push_back({i, r});
    vlast[a][r] = l;
    active[a].erase(b);
}

void add_friend (int a, int b, int i, vector<map<int, int>> &mv, vector<set<int>> &active, vector<map<int, bool>> &mstate) {
    if (mstate[a].count(b) == 0) {
        mstate[a][b] = true;
        mv[a][b] = vnext[a].size();
        vnext[a].push_back({});
        vlast[a].push_back(-1);
        id[a].push_back(b);
    }
    mstate[a][b] = true;
    auto it = active[a].upper_bound(b);
    int r = mv[a][*it];
    int l = mv[a][*prev(it)];
    int m = mv[a][b];
    vnext[a][l].push_back({i, m});
    vnext[a][m].push_back({i, r});
    vlast[a][m] = l;
    vlast[a][r] = m;
    active[a].insert(b);
}

void curseChanges(int U, int A[], int B[]) {
    vector<map<int, int>> mv (n, {{-1, 0}, {n, 1}});
    vector<map<int, bool>> mstate (n);
    vector<set<int>> active (n, {-1, n});
    for (int i = 0; i < U; i++) {
        int a = vid[A[i]];
        int b = vid[B[i]];
        if (active[a].count(b) != 0) {
            // remove friend
            rem_friend(a, b, i, mv, active, mstate);
            rem_friend(b, a, i, mv, active, mstate);
        } else {
            add_friend(a, b, i, mv, active, mstate);
            add_friend(b, a, i, mv, active, mstate);
        }
    }
}

int question(int x, int y, int v) {
    int x1 = vid[x];
    int y1 = vid[y];
    int sol = 1e9;
    int curl = (--upper_bound(vnext[x1][0].begin(), vnext[x1][0].end(), make_pair(v, -2)))->second;
    int curr = (--upper_bound(vnext[y1][0].begin(), vnext[y1][0].end(), make_pair(v, -2)))->second;
    int curr_next = (--upper_bound(vnext[y1][curr].begin(), vnext[y1][curr].end(), make_pair(v, -2)))->second;
    while (curl != 1) {
        while (curr != 1 && id[y1][curr_next] <= id[x1][curl]) {
            curr = curr_next;
            curr_next = (--upper_bound(vnext[y1][curr].begin(), vnext[y1][curr].end(), make_pair(v, -2)))->second;
        }
        if (curr != 1 && curr != 0 && curr != -1) {
            int nsol = abs(vhs[id[x1][curl]] - vhs[id[y1][curr]]);
            sol = min(sol, nsol);
        }
        if (curr_next != 1 && curr_next != 0 && curr_next != -1) {
            int nsol = abs(vhs[id[x1][curl]] - vhs[id[y1][curr_next]]);
            sol = min(sol, nsol);
        }
        curl = (--upper_bound(vnext[x1][curl].begin(), vnext[x1][curl].end(), make_pair(v, -2)))->second;
    }
    return sol;
}

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