| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1200261 | 12345678 | The Potion of Great Power (CEOI20_potion) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, k=50;
int n, m;
vector<int> h;
vector<set<pair<int, int>>> sv[nx];
vector<pair<int, int>> event[nx];
void init(int N, int D, int H[]) {
n=N;
for (int i=0; i<n; i++) h.push_back(H[i]);
for (int i=0; i<n; i++) event[i].push_back({0, 0}), sv[i].push_back(set<int> {});
}
void recalculate(int idx)
{
auto tmp=sv[idx].back();
for (int j=event[idx].size()-k; j<event[idx].size(); j++)
{
if (tmp.find({h[event[idx][j].second], event[idx][j].second})!=tmp.end()) tmp.erase({h[event[idx][j].second], event[idx][j].second});
else tmp.insert({h[event[idx][j].second], event[idx][j].second});
}
sv[idx].push_back(tmp);
}
vector<int> getstate(int idx, int date)
{
int t=lower_bound(event[idx].begin(), event[idx].end(), make_pair(date, INT_MAX))-event[idx].begin()-1;
int lst=(t)/k*k;
auto tmp=sv[idx][(t)/k];
for (int j=lst+1; j<=t; j++)
{
if (tmp.find({h[event[idx][j].second], event[idx][j].second})!=tmp.end()) tmp.erase({h[event[idx][j].second], event[idx][j].second});
else tmp.insert({h[event[idx][j].second], event[idx][j].second});
}
vector<int> ch;
for (auto x:tmp) ch.push_back(x.first); //cout<<"query "<<idx<<' '<<x<<'\n';
return ch;
}
void curseChanges(int U, int A[], int B[]) {
m=U;
for (int i=0; i<m; i++)
{
event[A[i]].push_back({i+1, B[i]});
if (event[A[i]].size()%k==1) recalculate(A[i]);
event[B[i]].push_back({i+1, A[i]});
if (event[B[i]].size()%k==1) recalculate(B[i]);
}
}
int question(int x, int y, int d) {
int res=1e9, idxy=0;
auto hx=getstate(x, d), hy=getstate(y, d);
for (int i=0; i<hx.size(); i++)
{
while (idxy+1<hy.size()&&hy[idxy+1]<=hx[i]) idxy++;
if (idxy<hy.size()) res=min(res, abs(hx[i]-hy[idxy]));
if (idxy+1<hy.size()) res=min(res, abs(hx[i]-hy[idxy+1]));
}
return res;
}