Submission #1264121

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

potion

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

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

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>{});
        T[i].push_back(0);
        ord[i].push_back(0);
    }
    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]);

        cnt[a[i]]++;
        cnt[b[i]]++;

        ord[a[i]].push_back(i);
        ord[b[i]].push_back(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(cnt[a[i]] == B) {
            g[a[i]].push_back(curr[a[i]]);
            T[a[i]].push_back(i);
            cnt[a[i]] = 0;
        }

        if(cnt[b[i]] == B) {
            g[b[i]].push_back(curr[b[i]]);
            T[b[i]].push_back(i);
            cnt[b[i]] = 0;
        }
    }

    for(int i=0; i<n; i++) {
        if(T[i].back() != m) {
            T[i].push_back(m);
            g[i].push_back(curr[i]);
        }
    }
}

int question(int x, int y, int v) {
    int ans = 1e9;
    
    int px = upper_bound(T[x].begin(), T[x].end(), v) - T[x].begin() - 1;
    int py = upper_bound(T[y].begin(), T[y].end(), v) - T[y].begin() - 1;
    set<int> stL = g[x][px];
    set<int> stR = g[y][py];

    int tx = upper_bound(ord[x].begin(), ord[x].end(), T[x][px]) - ord[x].begin();
    int ty = upper_bound(ord[y].begin(), ord[y].end(), T[y][py]) - ord[y].begin();

    for(int j=tx; j<ord[x].size(); j++) {
        if(ord[x][j] > v) break;
        int i = ord[x][j];
        // cout << x << " " << i << endl;
        if(a[i] == x) {
            if(stL.count(b[i]))
                stL.erase(b[i]);
            else
                stL.insert(b[i]);
        }
        if(b[i] == x) {
            if(stL.count(a[i]))
                stL.erase(a[i]);
            else
                stL.insert(a[i]);
        }
    }

    for(int j=ty; j<ord[y].size(); j++) {
        if(ord[y][j] > v) break;
        int i = ord[y][j];
        // cout << y << " " << i << endl;
        if(a[i] == y) {
            if(stR.count(b[i]))
                stR.erase(b[i]);
            else
                stR.insert(b[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