This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
}
Compilation message (stderr)
potion.cpp: In function 'void update(int, int, int, int, int, int, int)':
potion.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int mid=tl+tr>>1;
| ~~^~~
potion.cpp: In function 'void init(int, int, int)':
potion.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid=tl+tr>>1;
| ~~^~~
potion.cpp: In function 'void query(int, int, int, int, int, std::vector<int>&)':
potion.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid=tl+tr>>1;
| ~~^~~
potion.cpp: In function 'int main()':
potion.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0, j=0; i<V1.size(); i++)
| ~^~~~~~~~~~
potion.cpp:93:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(; j<V2.size() && V2[j]<=V1[i]; j++) ans=min(ans, V1[i]-V2[j]);
| ~^~~~~~~~~~
potion.cpp:94:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | if(j<V2.size()) ans=min(ans, V2[j]-V1[i]);
| ~^~~~~~~~~~
potion.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
54 | scanf("%d%d%d%d", &N, &D, &U, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:55:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | for(int i=1; i<=N; i++) scanf("%d", &H[i]);
| ~~~~~^~~~~~~~~~~~~
potion.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
potion.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
82 | scanf("%d%d%d", &x, &y, &v); x++; y++;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
/tmp/ccRpxXtI.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccL7XrLF.o:potion.cpp:(.text.startup+0x0): first defined here
/tmp/ccRpxXtI.o: In function `main':
grader.cpp:(.text.startup+0xde): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x167): undefined reference to `curseChanges(int, int*, int*)'
grader.cpp:(.text.startup+0x1c1): undefined reference to `question(int, int, int)'
collect2: error: ld returned 1 exit status