| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 349703 | Bill_00 | The Potion of Great Power (CEOI20_potion) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 200001
#define pb push_back
using namespace std;
int h[N],pre[N];
unordered_map<int,vector<int> >v[N];
vector<int>day[N];
void init(int n int d, int H[]){
for(int i=0;i<n;i++) h[i]=H[i];
}
void curseChanges(int u, int A[], int B[]){
for(int i=1;i<=u;i++){
int a=A[i-1],b=B[i-1];
day[a].pb(i);
day[b].pb(i);
if(pre[a]==0){
v[a][i].pb(b);
pre[a]=i;
}
else{
bool flag=0;
for(int j:v[a][pre[a]]){
if(j==b){
flag=1;
continue;
}
v[a][i].pb(j);
}
if(flag==0) v[a][i].pb(b);
pre[a]=i;
}
if(pre[b]==0){
v[b][i].pb(a);
pre[b]=i;
}
else{
bool flag=0;
for(int j:v[b][pre[b]]){
if(j==a){
flag=1;
continue;
}
v[b][i].pb(j);
}
if(flag==0) v[b][i].pb(a);
pre[b]=i;
}
}
}
int question(int x, int y, int z) {
int ans=1e9;
int id=upper_bound(day[x].begin(),day[x].end(),z)-day[x].begin();
--id;
if(id<0){
return ans;
}
int a=day[x][id];
id=upper_bound(day[y].begin(),day[y].end(),z)-day[y].begin();
--id;
if(id<0){
return ans;
}
int b=day[y][id];
// cout << a << ' ' << b << '\n';
if(v[x][a].size()==0 || v[y][b].size()==0){
return ans;
}
vector<int>xx,yy;
for(int V:v[y][b]){
yy.pb(h[V]);
}
sort(yy.begin(),yy.end());
for(int U:v[x][a]){
int id=lower_bound(yy.begin(),yy.end(),h[U])-yy.begin();
ans=min(ans,abs(h[U]-yy[max(0,id-1)]));
ans=min(ans,abs(yy[id]-h[U]));
}
return ans;
}