Submission #1264096

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

potion

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int B = 100;

set<int> curr[N];
vector<set<int> > g[N];
int n, D, h[N], a[N], b[N], m;

bool cmp(int i, int j) {
    return h[i] < h[j];
}

void init(int _N, int _D, int H[]) {
    n = _N;
    D = _D;
    for(int i=0; i<n; i++) h[i] = H[i];
}   

void curseChanges(int U, int _A[], int _B[]) {
    m = U;
    for(int i=0; i<n; i++) g[i].push_back(set<int>{});
    for(int i=1; i<=m; i++) {
        a[i] = _A[i-1];
        b[i] = _B[i-1];
        if(a[i] > b[i]) swap(a[i], b[i]);

        if(curr[a[i]].count(b[i])) {
            curr[a[i]].erase(b[i]);
            curr[b[i]].erase(a[i]);
        } else {
            curr[a[i]].insert(b[i]);
            curr[b[i]].insert(a[i]);
        }

        if(i % B == 0) {
            for(int j=0; j<n; j++)
                g[j].push_back(curr[j]);
        }
    }
}

int question(int x, int y, int v) {
    int ans = 1e9;
    
    int id = v / B;
    set<int> stL = g[x][id];
    set<int> stR = g[y][id];

    for(int i=id*B+1; i<=v; i++) {
        if(a[i] == x) {
            if(stL.count(b[i]))
                stL.erase(b[i]);
            else
                stL.insert(b[i]);
        }
        if(a[i] == y) {
            if(stR.count(b[i]))
                stR.erase(b[i]);
            else
                stR.insert(b[i]);
        }
        if(b[i] == x) {
            if(stL.count(a[i]))
                stL.erase(a[i]);
            else
                stL.insert(a[i]);
        }
        if(b[i] == y) {
            if(stR.count(a[i]))
                stR.erase(a[i]);
            else
                stR.insert(a[i]);
        }
    }

    vector<int> L(stL.begin(), stL.end());
    vector<int> R(stR.begin(), stR.end());
    if(L.empty() || R.empty()) return 1e9;
    sort(L.begin(), L.end(), cmp);
    sort(R.begin(), R.end(), cmp);

    int j = 0;
    for(int i=0; i<R.size(); i++) {
        while(j+1 < L.size() && h[L[j+1]] <= h[R[i]]) j++;
        ans = min(ans, abs(h[L[j]] - h[R[i]]));
    }

    j = L.size() - 1;
    for(int i=R.size()-1; i>=0; i--) {
        while(j && h[L[j-1]] >= h[R[i]]) j--;
        ans = min(ans, abs(h[L[j]] - h[R[i]]));
    }

    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