Submission #1159185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159185		adiyer	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	173 ms	33124 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];

vector < int > val[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 < n; i++) st[i].clear();
    for(int i = 0; i < m; i++) a[i] = A[i], b[i] = B[i];
    for(int i = 0; i < m; 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]);
    }
    for(int i = 0; i < n; i++){
        for(auto it : st[i]) val[i].push_back(h[it]);
        sort(all(val[i]));
    }
}

int question(int x, int y, int v) {
    int ans = 1000000000, j = 0;
    for(int i = 0; i < val[x].size(); i++){
        if(j == val[y].size()) break;
        while(j + 1 < val[y].size() && val[y][j + 1] < val[x][i]) j++;
        ans = min(ans, abs(val[x][i] - val[y][j]));
        if(j + 1 < val[x].size()) ans = min(ans, abs(val[y][j + 1] - val[x][i]));
        if(j - 1 >= 0) ans = min(ans, abs(val[y][j - 1] - val[x][i]));
    }
    return ans;
}


/* 
Test g++ grader.cpp potion.cpp -o program.exe
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
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/

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