| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 294556 | nandonathaniel | The Potion of Great Power (CEOI20_potion) | C++14 | 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;
const int MAXN=100005;
int h[MAXN],C[MAXN],n,D;
vector<pii> adj[MAXN];
vector<vector<int> > preCompute[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[]) {
for(int i=0;i<U;i++){
adj[A[i]].push_back({B[i],i+1});
adj[B[i]].push_back({A[i],i+1});
}
for(int i=0;i<n;i++){
C[i]=(int)sqrt((int)adj[i].size());
if(C[i]==0)C[i]=1;
set<int> S;
preCompute[i].push_back(vector<int>());
for(int j=0;j<adj[i].size();j++){
if(S.count(adj[i][j].first)){
S.erase(adj[i][j].first);
}
else S.insert(adj[i][j].first);
if((j+1)%C[i]==0){
preCompute[i].push_back(vector<int>());
for(int isi : S)preCompute[i].back().push_back(isi);
}
}
}
}
bitset<100005> stat;
int question(int a, int b, int d) {
int ans=1e9;
if(d==0){
return ans;
}
int ki=0,ka=adj[a].size()-1,res=-1;
while(ki<=ka){
int mid=(ki+ka)/2;
if(adj[a][mid].second<=d){
res=mid;
ki=mid+1;
}
else ka=mid-1;
}
stat.reset();
vector<int> A;
if(res!=-1){
for(auto isi : preCompute[a][res/C[a]])stat[isi]=true;
for(int i=(res/C[a])*C[a];i<=res;i++){
stat[adj[a][i].first]=stat[adj[a][i].first]^1;
}
for(auto isi : preCompute[a][res/C[a]]){
if(stat[isi])A.push_back(h[isi]);
}
for(int i=(res/C[a])*C[a];i<=res;i++){
if(stat[adj[a][i].first])A.push_back(h[adj[a][i].first]);
}
}
ki=0;ka=adj[b].size()-1;res=-1;
while(ki<=ka){
int mid=(ki+ka)/2;
if(adj[b][mid].second<=d){
res=mid;
ki=mid+1;
}
else ka=mid-1;
}
stat.reset();
vector<int> B;
if(res!=-1){
for(auto isi : preCompute[b][res/C[b]])stat[isi]=true;
for(int i=(res/C[b])*C[b];i<=res;i++){
stat[adj[b][i].first]=stat[adj[b][i].first]^1;
}
for(auto isi : preCompute[b][res/C[b]]){
if(stat[isi])B.push_back(h[isi]);
}
for(int i=(res/C[b])*C[b];i<=res;i++){
if(stat[adj[b][i].first])B.push_back(h[adj[b][i].first]);
}
}
sort(A.begin(),A.end());
sort(B.begin(),B.end());
int x=0,y=0;
while(x<(int)A.size() && y<(int)B.size()){
ans=min(ans,abs(A[x]-B[y]));
if(A[x]<B[y])x++;
else y++;
}
return ans;
}