| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 798761 | PoonYaPat | 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>
#include "grader.cpp"
using namespace std;
typedef pair<int,vector<int>> piv;
typedef pair<int,int> pii;
int n,h[100005];
const int sq=300;
vector<pii> c[100005];
vector<piv> v[100005];
bool comp(int a, int b) {return h[a]<h[b];}
void init(int N, int D, int H[]) {
n=N;
for (int i=0; i<n; ++i) h[i]=H[i], v[i].push_back(piv(0,{}));
}
void curseChanges(int U, int A[], int B[]) {
for (int i=0; i<U; ++i) {
c[A[i]].push_back(pii(i+1,B[i]));
c[B[i]].push_back(pii(i+1,A[i]));
}
for (int i=0; i<n; ++i) {
vector<int> temp,temp2;
v[i].push_back(piv(0,{}));
for (int j=0; j<c[i].size(); ++j) {
int add=c[i][j].second;
bool have=false;
for (auto s : temp) if (s==add) have=true;
if (have) {
for (auto s : temp) if (s!=add) temp2.push_back(s);
} else {
bool f=false;
for (auto s : temp) {
if (h[s]<h[add]) temp2.push_back(s);
else {
if (!f) {
temp2.push_back(add);
temp2.push_back(s);
} else temp2.push_back(s);
}
}
if (!f) temp2.push_back(add);
}
swap(temp,temp2);
temp2.clear();
if ((j+1)%sq==0) v[i].push_back(piv(c[i][j].first,temp));
}
}
}
int question(int x, int y, int day) {
int hx=upper_bound(v[x].begin(),v[x].end(),piv(day+1,{}))-v[x].begin()-1;
int hy=upper_bound(v[y].begin(),v[y].end(),piv(day+1,{}))-v[y].begin()-1;
vector<int> tempx=v[x][hx].second,tempy=v[y][hy].second;
map<int,int> haveX,haveY;
for (auto s : tempx) haveX[s]++;
for (auto s : tempy) haveY[s]++;
int Hx=upper_bound(c[x].begin(),c[x].end(),pii(v[x][hx].first,INT_MAX))-c[x].begin();
while (Hx<c[x].size() && c[x][Hx].first<=day) tempx.push_back(c[x][Hx].second), ++haveX[c[x][Hx].second], ++Hx;
int Hy=upper_bound(c[y].begin(),c[y].end(),pii(v[y][hy].first,INT_MAX))-c[y].begin();
while (Hy<c[y].size() && c[y][Hy].first<=day) tempy.push_back(c[y][Hy].second), ++haveY[c[y][Hy].second], ++Hy;
sort(tempx.begin(),tempx.end(),comp);
sort(tempy.begin(),tempy.end(),comp);
int xi=0, yi=0, nx=tempx.size(), ny=tempy.size();
int ans=1e9;
while (xi<nx && yi<ny) {
if (haveX[tempx[xi]]%2==0) ++xi;
else if (haveY[tempy[yi]]%2==0) ++yi;
else {
ans=min(ans,abs(h[tempx[xi]]-h[tempy[yi]]));
if (h[tempx[xi]]>h[tempy[yi]]) ++yi;
else ++xi;
}
}
return ans;
}