Submission #1159131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159131		adiyer	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	3097 ms	27052 KiB

potion

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n, m, d;
int h[MAXN], a[MAXN], b[MAXN];

set < int > st[MAXN];

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 < m; i++) a[i] = A[i], b[i] = B[i];
}

int question(int x, int y, int v) {
    for(int i = 0; i < v; i++){
        if(st[a[i]].find(b[i]) == st[a[i]].end()) st[a[i]].insert(b[i]), st[b[i]].insert(a[i]);
        else st[a[i]].erase(b[i]), st[b[i]].erase(a[i]);
    }
    vector < int > val1, val2;
    for(auto it : st[x]) val1.push_back(h[it]);
    for(auto it : st[y]) val2.push_back(h[it]);
    int ans = 1000000000, j = 0;
    sort(all(val1)), sort(all(val2));
    if(val1.empty() || val2.empty()) return 1000000000;
    for(int i = 0; i < val2.size(); i++){
        while(val1[j + 1] < val2[i] && j + 1 < val1.size()) j++;
        ans = min(ans, abs(val1[j] - val2[i]));
        if(j + 1 < val1.size()) ans = min(ans, abs(val1[j + 1] - val2[i]));
    }
    return ans;
}


/* 
Test
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
*/

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