| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 498032 | andrei_boaca | 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>
//#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
const int C=50;
int n,d,u,q,h[100005],p1[200005],p2[200005];
unordered_set<int> setik[100005];
vector<int> vals[100005];
vector< pair< int, vector<int> > > checkpoint[100005];
vector<int> ck[100005];
vector<int> v;
vector<int> v1;
vector<int> rez;
vector<int> V1,V2;
pii day[200005];
bool isthere[200005];
int findpoz(int poz,int who)
{
if(day[poz].first==who)
return p1[poz];
else
return p2[poz];
}
void buildv(int x,int zi,int index)
{
rez.clear();
v1.clear();
int st=0;
int dr=checkpoint[x].size();
int pozmax=-1;
dr--;
while(st<=dr)
{
int mij=(st+dr)/2;
if(checkpoint[x][mij].first<=zi)
{
pozmax=max(pozmax,mij);
st=mij+1;
}
else
dr=mij-1;
}
unordered_set<int> t;
if(pozmax!=-1)
{
for(int i=0;i<checkpoint[x][pozmax].second.size();i++)
{
int p=checkpoint[x][pozmax].second[i];
v1.push_back(p);
isthere[p]=1;
}
int poz=findpoz(checkpoint[x][pozmax].first,x);
int nrit=0;
for(int i=poz+1;i<vals[x].size()&&vals[x][i]<=zi;i++)
{
nrit++;
int z=vals[x][i];
int nod=(x^day[z].first^day[z].second);
t.insert(nod);
if(isthere[nod]==0)
isthere[nod]=1;
else
isthere[nod]=0;
}
assert(nrit<=C);
}
if(!t.empty())
{
for(int j:t)
v1.push_back(j);
}
if(v1.empty())
{
if(index==1)
V1=rez;
else
V2=rez;
return;
}
for(int i=0;i<v1.size();i++)
if(isthere[v1[i]]==1)
{
rez.push_back(h[v1[i]]);
isthere[v1[i]]=0;
}
sort(rez.begin(),rez.end());
assert((int)rez.size()<=d);
if(index==1)
V1=rez;
else
V2=rez;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d>>u>>q;
for(int i=1;i<=n;i++)
cin>>h[i-1];
for(int i=1;i<=u;i++)
{
int a,b;
cin>>a>>b;
day[i]={a,b};
vals[a].push_back(i);
p1[i]=vals[a].size();
p1[i]--;
vals[b].push_back(i);
p2[i]=vals[b].size();
p2[i]--;
if(setik[a].find(b)!=setik[a].end())
{
setik[a].erase(b);
setik[b].erase(a);
}
else
{
setik[a].insert(b);
setik[b].insert(a);
}
if((int)vals[a].size()%C==1)
{
vector<int> aux;
for(int j:setik[a])
aux.push_back(j);
checkpoint[a].push_back({i,aux});
}
if((int)vals[b].size()%C==1)
{
vector<int> aux;
for(int j:setik[b])
aux.push_back(j);
checkpoint[b].push_back({i,aux});
}
}
while(q--)
{
int x,y,zi;
cin>>x>>y>>zi;
V1.clear();
V2.clear();
buildv(x,zi,1);
buildv(y,zi,2);
if(V1.empty()||V2.empty())
{
cout<<1000000000<<endl;
continue;
}
int ans=1e9;
int j=0;
for(int i=0;i<V1.size();i++)
{
j=max(j,0);
while(j<V2.size()&&V2[j]<=V1[i])
j++;
j--;
if(j>=0)
ans=min(ans,abs(V1[i]-V2[j]));
if(j+1<V2.size())
ans=min(ans,abs(V1[i]-V2[j+1]));
}
cout<<ans<<endl;
}
return 0;
}