Submission #477709

#	Time	Username	Problem	Language	Result	Execution time	Memory
477709		InternetPerson10	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	1052 ms	262148 KiB

potion

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> pas;
vector<int> heights, m;
set<int> ses[100001];
set<int> savs[400001];
vector<vector<int>> upd;

int n;

void init(int N, int D, int H[]) {
    n = N;
    pas.resize(n);
    heights.resize(n);
    m.resize(n);
    upd.resize(n);
    for(int i = 0; i < n; i++) {
        pas[i].first = H[i];
        pas[i].second = i;
        ses[i] = set<int>();
    }
    sort(pas.begin(), pas.end());
    for(int i = 0; i < n; i++) {
        m[pas[i].second] = i;
        heights[i] = pas[i].first;
    }
    for(int i = 0; i < n; i++) {
        upd[i].push_back(-1);
    }
}

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < U; i++) {
        int x = A[i], y = B[i];
        x = m[x]; y = m[y];
        auto it1 = ses[x].find(y);
        if(it1 == ses[x].end()) {
            ses[x].insert(y);
            ses[y].insert(x);
        }
        else {
            ses[x].erase(y);
            ses[y].erase(x);
        }
        upd[x].push_back(2*i);
        upd[y].push_back(2*i+1);
        savs[2*i] = ses[x];
        savs[2*i+1] = ses[y];
    }
}

int question(int x, int y, int v) {
    v--;
    x = m[x]; y = m[y];
    int ans = 1000000000;
    auto itxx = upper_bound(upd[x].begin(), upd[x].end(), 2*v+1);
    itxx--;
    auto ityy = upper_bound(upd[y].begin(), upd[y].end(), 2*v+1);
    ityy--;
    if(*ityy == -1 || *itxx == -1) return ans;
    set<int> sx = savs[*itxx]; 
    set<int> sy = savs[*ityy]; 
    auto itx = sx.begin();
    auto ity = sy.begin();
    while(itx != sx.end() && ity != sy.end()) {
        ans = min(ans, abs(heights[*itx] - heights[*ity]));
        if(heights[*itx] < heights[*ity]) itx++;
        else if(heights[*itx] > heights[*ity]) ity++;
        else {
            return 0;
        }
    }
    return ans;
}

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