| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 612038 | 2022-07-29T10:21:30 Z | 1bin | The Potion of Great Power (CEOI20_potion) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define all(v) v.begin(), v.end()
const int NMAX = 1e5 + 5;
const int sqt = 50;
int n, d, u, q, h[NMAX], a, b;
vector<int> ix[NMAX], l, r;
vector<vector<pair<int, int>>> v[NMAX];
void init(int N, int D, int H[]){
n = N; d = D;
for(int i = 0; i < n; i++) h[i] = H[i];
return;
}
void chk(int x, int A[], int B[]){
int sz = ix[x].size();
if(sz % sqt) return;
set<pair<int, int>> s;
if(--sz) for(auto& t : v[x].back()) s.emplace(t);
for(int i = sz * sqt; i < sz * sqt + sqt; i++){
int y = (A[ix[x][i]] == x) ? B[ix[x][i]] : A[ix[x][i]];
if(s.find({h[y], y}) == s.end()) s.insert({h[y], y});
else s.erase({h[y], y});
}
vector<pair<int, int>> tmp;
for(auto t : s) tmp.emplace_back(t);
v[x].emplace_back(tmp);
return;
}
void curseChanges(int U, int A[], int B[]){
u = U;
for(int i = 0; i < u; i++){
a = A[i]; b = B[i];
ix[a].emplace_back(i);
ix[b].emplace_back(i);
chk(a, A, B); chk(b, A, B);
}
return;
}
int question(int x, int y, int V){
int ans = 1e9, xi, yi, xb, yb, hx, hy, iix, iiy;
int xsz = lower_bound(all(ix[x]), V) - ix[x].begin();
int ysz = lower_bound(all(ix[y]), V) - ix[y].begin();
xb = xsz / sqt * sqt; yb = ysz / sqt * sqt;
xi = yi = 0;
while(xi < xb && yi < yb){
hx = v[x][xi / sqt][xi].fi;
hy = v[y][yi / sqt][yi].fi;
ans = min(ans, abs(hx - hy));
hx < hy ? xi++ : yi++;
}
xi = xb; yi = 0;
while(xi < xsz && yi < yb){
hx = v[x][xi / sqt][xi].fi;
hy = v[y][yi / sqt][yi].fi;
ans = min(ans, abs(hx - hy));
hx < hy ? xi++ : yi++;
}
xi = 0; yi = yb;
while(xi < xb && yi < ysz){
hx = v[x][xi / sqt][xi].fi;
hy = v[y][yi / sqt][yi].fi;
ans = min(ans, abs(hx - hy));
hx < hy ? xi++ : yi++;
}
xi = yb; yi = yb;
while(xi < xsz && yi < ysz){
hx = v[x][xi / sqt][xi].fi;
hy = v[y][yi / sqt][yi].fi;
ans = min(ans, abs(hx - hy));
hx < hy ? xi++ : yi++;
}
return ans;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
return 0;
}