| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 343471 | leinad2 | The Potion of Great Power (CEOI20_potion) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int n, d, H[100010], i, j, u, A[200010], B[200010], b, x, a;
set<int>adj[100010][450], F[100010], X;
set<int>::iterator it, it2;
void init(int N, int D, int X[])
{
n=N;
d=D;
for(i=0;i<n;i++)H[i]=X[i];
}
void curseChanges(int U, int C[], int D[])
{
u=U;
for(i=0;i++<u;)A[i]=C[i-1],B[i]=D[i-1];
b=(int)round(sqrt(u));
for(i=0;i++<u;)
{
if(F[B[i]].find(A[i])==F[B[i]].end())
{
F[A[i]].insert(B[i]);
F[B[i]].insert(A[i]);
}
else
{
F[A[i]].erase(B[i]);
F[B[i]].erase(A[i]);
}
if(i%b==0)
{
for(j=0;j<n;j++)
{
for(it=F[j].begin();it!=F[j].end();it++)
{
adj[j][i/b].insert(*it);
}
}
}
}
}
int question(int s, int e, int v)
{
x=v/b;
for(i=b*x+1;i<=v;i++)
{
if(adj[B[i]][x].find(A[i])==adj[B[i]][x].end())
{
adj[A[i]][x].insert(B[i]);
adj[B[i]][x].insert(A[i]);
}
else
{
adj[A[i]][x].erase(B[i]);
adj[B[i]][x].erase(A[i]);
}
}
int ans=1e9;
if(adj[s][x].size()==0||adj[e][x].size()==0)
{
goto w;
}
X.clear();
for(it=adj[s][x].begin();it!=adj[s][x].end();it++)
{
X.insert(H[*it]);
}
for(it=adj[e][x].begin();it!=adj[e][x].end();it++)
{
it2=X.lower_bound(H[*it]);
if(it2==X.end())it2--;
ans=min(ans, abs(H[*it]-*it2));
if(it2==X.begin())continue;
it2--;
ans=min(ans, abs(H[*it]-*it2));
}
w:;
for(i=v;i>b*x;i--)
{
if(adj[B[i]][x].find(A[i])==adj[B[i]][x].end())
{
adj[A[i]][x].insert(B[i]);
adj[B[i]][x].insert(A[i]);
}
else
{
adj[A[i]][x].erase(B[i]);
adj[B[i]][x].erase(A[i]);
}
}
return ans;
}