| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1230080 | Gray | The Potion of Great Power (CEOI20_potion) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops")#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
vector<int> h;
int n, mxd, d;
vector<vector<vector<int>>> A;
vector<vector<ll>> tA;
void init(int N, int D, int H[]) {
n=N; mxd=D; h.resize(n);
for (int i=0; i<n; i++) h[i]=H[i];
}
void curseChanges(int U, int u[], int v[]) {
A.resize(n); tA.resize(n); d=U;
for (int i=0; i<n; i++) {
A[i].push_back(vector<int>()); tA[i].push_back(0);
}
set<ll> temp; vector<int> t2;
for (int i=0; i<U; i++){
temp.clear();
for (auto x:A[u[i]].back()) temp.insert(x);
tA[u[i]].push_back(i+1); tA[v[i]].push_back(i+1);
if (temp.count(v[i])){
t2.clear();
for (auto x:A[u[i]].back()){
if (x==v[i]) continue;
t2.push_back(x);
}
A[u[i]].push_back(t2);
t2.clear();
for (auto x:A[v[i]].back()){
if (x==u[i]) continue;
t2.push_back(x);
}
A[v[i]].push_back(t2);
}else{
A[u[i]].push_back(A[u[i]].back());
A[u[i]].back().push_back(v[i]);
A[v[i]].push_back(A[v[i]].back());
A[v[i]].back().push_back(u[i]);
}
}
}
vector<int> hs;
int question(int x, int y, int v) {
ll indx = upper_bound(tA[x].begin(), tA[x].end(), v)-tA[x].begin()-1;
hs.clear();
for (auto u:A[x][indx]){
hs.push_back(h[u]);
}
if (hs.empty()) return 1e9;
sort(hs.begin(), hs.end());
hs.erase(unique(hs.begin(), hs.end()), hs.end());
int mn=1e9;
int indy = upper_bound(tA[y].begin(), tA[y].end(), v)-tA[y].begin()-1;
for (auto u:A[y][indy]){
ll ind = lower_bound(hs.begin(), hs.end(), h[u])-hs.begin();
if (ind<(ll)hs.size()){
mn=min(mn, hs[ind]-h[u]);
}
if (ind){
mn=min(mn, h[u]-hs[ind-1]);
}
}
return mn;
}