| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 259699 | Kastanda | New Home (APIO18_new_home) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
using namespace std;
const int N = 300005, INF = 1e9 + 9;
int n, q, k, X[N], T[N], L[N], R[N], Y[N], Z[N], RS[N];
vector < int > U;
multiset < int > ST[N];
struct Set {
priority_queue < int > PQ, DL;
inline void Insert(int val) {
PQ.push(val);
}
inline void Delete(int val) {
DL.push(val);
}
inline int GetMax() {
while (DL.size() && DL.top() == PQ.top())
DL.pop(), PQ.pop();
return PQ.size() ? PQ.top() : INT_MIN;
}
};
Set D[N * 2][2];
inline int GetId(int val)
{
return (int)(lower_bound(U.begin(), U.end(), val) - U.begin());
}
inline void Add(int l, int r, int a, int b)
{
l += (int)U.size();
r += (int)U.size();
for (; l < r; l >>= 1, r >>= 1)
{
if (l & 1) D[l][a].Insert(b), l ++;
if (r & 1) r --, D[r][a].Insert(b);
}
}
inline void Del(int l, int r, int a, int b)
{
l += (int)U.size();
r += (int)U.size();
for (; l < r; l >>= 1, r >>= 1)
{
if (l & 1) D[l][a].Delete(b), l ++;
if (r & 1) r --, D[r][a].Delete(b);
}
}
inline pair < int , int > Get(int i)
{
pair < int , int > rt = {-INF, -INF};
for (i += (int)U.size(); i; i >>= 1)
{
rt.first = max(rt.first, D[i][0].GetMax());
rt.second = max(rt.second, D[i][1].GetMax());
}
return rt;
}
inline void Adder(int l, int r, int a, int b)
{
l = GetId(l);
r = GetId(r);
Add(l, r, a, b);
}
inline void Deler(int l, int r, int a, int b)
{
l = GetId(l);
r = GetId(r);
Del(l, r, a, b);
}
inline void Do(int l, int r)
{
int mid = (l + r + 1) >> 1
// [l, mid)
Adder(l, mid, 1, -l);
// [mid, r]
Adder(mid, r + 1, 0, r);
}
inline void Undo(int l, int r)
{
int mid = (l + r + 1) >> 1;
// [l, mid)
Deler(l, mid, 1, -l);
// [mid, r]
Deler(mid, r + 1, 0, r);
}
inline void Add(int tp, int x)
{
auto it = ST[tp].lower_bound(x);
assert(it != ST[tp].end());
if (* it == x)
return void(ST[tp].insert(x));
int r = * it; it --;
int l = * it;
Undo(l, r);
Do(l, x);
Do(x, r);
ST[tp].insert(x);
}
inline void Del(int tp, int x)
{
auto it = ST[tp].lower_bound(x);
assert(* it == x);
it = ST[tp].erase(it);
if (* it == x)
return ;
int r = * it; it --;
int l = * it;
Undo(l, x);
Undo(x, r);
Do(l, r);
}
int main()
{
scanf("%d%d%d", &n, &k, &q);
vector < pair < int , int > > E;
for (int i = 1; i <= n; i ++)
{
scanf("%d%d%d%d", &X[i], &T[i], &L[i], &R[i]);
E.push_back({L[i], -i});
E.push_back({R[i] + 1, -i});
}
for (int i = 1; i <= q; i ++)
{
scanf("%d%d", &Y[i], &Z[i]);
E.push_back({Z[i], i});
U.push_back(Y[i]);
}
sort(E.begin(), E.end());
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
for (int i = 1; i <= k; i ++)
{
ST[i].insert(-INF);
ST[i].insert(INF);
Do(-INF, INF);
}
for (auto e : E)
{
int i = e.second;
if (i < 0)
{
i = -i;
if (e.first == L[i])
Add(T[i], X[i]);
else
Del(T[i], X[i]);
continue;
}
int y = GetId(Y[i]);
pair < int , int> rt = Get(y);
RS[i] = max(rt.first - Y[i], rt.second + Y[i]);
if (RS[i] > (int)1e8)
RS[i] = -1;
}
for (int i = 1; i <= q; i ++)
printf("%d\n", RS[i]);
return 0;
}