Submission #1055835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055835		TAhmed33	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	2659 ms	262144 KiB

potion

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
//#include "grader.cpp"
const int MAXN = 1e5 + 25;
const int B = 300;
int n, d, h[MAXN];
void init(int N, int D, int H[]) {
    n = N; d = D;
    for (int i = 0; i < n; i++) {
        h[i] = H[i];
    }
}
int u, a[MAXN], b[MAXN];
map <int, vector <int>> adj[MAXN / B + 1];
void curseChanges(int U, int A[], int BB[]) {
    u = U;
    for (int i = 0; i < u; i++) {
        a[i] = A[i]; b[i] = BB[i];
    }
    int ptr = 0;
    int cnt = 0;
    set <pair <int, int>> dd;
    for (int i = 0; i < u; i += B) {
        for (auto [x, y] : dd) {
            adj[cnt][x].push_back(y);
            adj[cnt][y].push_back(x);
        }
        for (int j = i; j <= min(u - 1, i + B - 1); j++) {
            if (dd.count({a[j], b[j]})) {
                dd.erase({a[j], b[j]});
            } else {
                dd.insert({a[j], b[j]});
            }
        }
        cnt++;
    }
}

int question (int x, int y, int v) {
    set <int> g, h2;
    for (auto j : adj[v / B][x]) {
        g.insert(j);
    }
    for (auto j : adj[v / B][y]) {
        h2.insert(j);
    }
/*    for (auto j : g) {
        cout << j << " ";
    }
    cout << '\n';
    for (auto j : h2) {
        cout << j << " ";
    }
    cout << '\n';*/
    for (int i = B * (v / B); i < v; i++) {
        if (a[i] == x) {
            if (g.count(b[i])) {
                g.erase(b[i]);
            } else {
                g.insert(b[i]);
            }
        } else if (b[i] == x) {
            if (g.count(a[i])) {
                g.erase(a[i]);
            } else {
                g.insert(a[i]);
            }
        }
        if (a[i] == y) {
            if (h2.count(b[i])) {
                h2.erase(b[i]);
            } else {
                h2.insert(b[i]);
            }
        } else if (b[i] == y) {
            if (h2.count(a[i])) {
                h2.erase(a[i]);
            } else {
                h2.insert(a[i]);
            }
        }
    }
/*    for (auto j : g) {
        cout << j << " ";
    }
    cout << '\n';
    for (auto j : h2) {
        cout << j << " ";
    }
    cout << '\n';*/
    multiset <int> xx, yy;
    for (auto j : g) {
        xx.insert(h[j]);
    }
    for (auto j : h2) {
        yy.insert(h[j]);
    }
/*    for (auto j : xx) {
        cout << j << " ";
    }
    cout << '\n';
    for (auto j : yy) {
        cout << j << " ";
    }
    cout << '\n';*/
    int mn = 1e9;
    for (auto j : xx) {
        auto k = yy.lower_bound(j);
        if (k != yy.end()) {
            mn = min(mn, (*k) - j);
        }
        if (k != yy.begin()) {
            k--;
            mn = min(mn, j - *k);
        }
    }
    return mn;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:21:9: warning: unused variable 'ptr' [-Wunused-variable]
   21 |     int ptr = 0;
      |         ^~~

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