# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1231037 | poat | The Potion of Great Power (CEOI20_potion) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
// #include "grader.cpp"
using namespace std;
const int N = 2e5 + 100, C = 500;
int n, D, H[N];
int U, A[N], B[N];
vector<int> vec[C][N];
set<int> S[N];
void init(int NN, int DD, int HH[])
{
n = NN;
D = DD;
for(int i = 0; i < n; i++)
H[i] = HH[i];
}
void curseChanges(int u, int AA[], int BB[])
{
for(int i = 0; i < u; i++)
{
A[i + 1] = AA[i];
B[i + 1] = BB[i];
}
U = u;
for(int i = 1; i <= u; i++)
{
int a = A[i], b = B[i];
if(S[a].find(b) != S[a].end())
{
S[a].erase(b);
S[b].erase(a);
}
else
{
S[a].insert(b);
S[b].insert(a);
}
if(i % C == 0)
{
int ind = i / C;
for(int j = 0; j < n; j++)
{
for(auto h : S[j])
vec[ind][j].push_back(h);
}
}
}
// for(int i = 1; i <= 3; i++)
// {
// cout << i << " == \n";
// for(int j = 0; j < n; j++)
// {
// cout << j << " == ";
// for(auto h : vec[i][j])
// cout << h << ' ';
// cout << '\n';
// }
// cout << '\n';
// }
// exit(0);
}
set<int> S1, S2;
vector<int> V1, V2;
int question(int x, int y, int v)
{
S1.clear();
S2.clear();
V1.clear();
V2.clear();
int ind = (v / C);
for(auto i : vec[ind][x])
S1.insert(i);
for(auto i : vec[ind][y])
S2.insert(i);
ind *= C;
for(int i = ind + 1; i <= v; i++)
{
if(A[i] == x || B[i] == x)
{
int k = (A[i] == x ? B[i] : A[i]);
if(S1.find(k) != S1.end())
S1.erase(k);
else
S1.insert(k);
}
if(A[i] == y || B[i] == y)
{
int k = (A[i] == y ? B[i] : A[i]);
if(S2.find(k) != S2.end())
S2.erase(k);
else
S2.insert(k);
}
}
for(auto i : S1)
V1.push_back(H[i]);
for(auto i : S2)
V2.push_back(H[i]);
int res = 1e9;
for(auto i : V1)
{
ind = lower_bound(V2.begin(), V2.end(), i) - V2.begin();
if(ind != V2.size())
res = min(res, V2[ind] - i);
if(ind)
res = min(res, i - V2[ind - 1]);
}
return res;
}