| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 292934 | arnold518 | The Potion of Great Power (CEOI20_potion) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXD = 500;
const int MAXU = 2e5;
const int MAXQ = 5e4;
int N, D, U, Q;
int H[MAXN+10];
map<pii, int> M;
vector<pii> tree[MAXU*4+10];
void update(int node, int tl, int tr, int l, int r, int u, int v)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
tree[node].push_back({u, v});
tree[node].push_back({v, u});
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, u, v);
update(node*2+1, mid+1, tr, l, r, u, v);
}
void init(int node, int tl, int tr)
{
sort(tree[node].begin(), tree[node].end());
if(tl==tr) return;
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
}
void query(int node, int tl, int tr, int p, int u, vector<int> &V)
{
auto it=lower_bound(tree[node].begin(), tree[node].end(), pii(u, 0));
auto jt=lower_bound(tree[node].begin(), tree[node].end(), pii(u+1, 0));
for(auto pt=it; pt!=jt; pt++) V.push_back(H[pt->second]);
if(tl==tr) return;
int mid=tl+tr>>1;
if(p<=mid) query(node*2, tl, mid, p, u, V);
else query(node*2+1, mid+1, tr, p, u, V);
}
int main()
{
scanf("%d%d%d%d", &N, &D, &U, &Q);
for(int i=1; i<=N; i++) scanf("%d", &H[i]);
for(int i=1; i<=U; i++)
{
int u, v;
scanf("%d%d", &u, &v);
u++; v++;
if(u>v) swap(u, v);
if(M.find({u, v})!=M.end())
{
update(1, 0, U, M[{u, v}], i-1, u, v);
M.erase({u, v});
}
else
{
M[{u, v}]=i;
}
}
for(auto it : M)
{
update(1, 0, U, it.second, U, it.first.first, it.first.second);
}
init(1, 0, U);
while(Q--)
{
int x, y, v;
scanf("%d%d%d", &x, &y, &v); x++; y++;
vector<int> V1, V2;
query(1, 0, U, v, x, V1);
query(1, 0, U, v, y, V2);
sort(V1.begin(), V1.end());
sort(V2.begin(), V2.end());
int ans=1e9;
for(int i=0, j=0; i<V1.size(); i++)
{
for(; j<V2.size() && V2[j]<=V1[i]; j++) ans=min(ans, V1[i]-V2[j]);
if(j<V2.size()) ans=min(ans, V2[j]-V1[i]);
}
printf("%d\n", ans); fflush(stdout);
}
}