1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef multiset<int>::iterator IT;
const int N = 600010, LG = 20, INF = 1000000000;
int n, k, m, ans[N], clr;
struct Q {
int opt, pos, type, pri;
Q(int Opt = 0, int Pos = 0, int Type = 0, int Pri = 0) :
opt(Opt), pos(Pos), type(Type), pri(Pri) {}
inline bool operator<(const Q &yy)const {
return pri == yy.pri ? opt < yy.opt : pri < yy.pri;
}
}; Q q[N + N]; int len;
multiset<int> pp[N], st[N * LG];
int rt, tot, cnt, lf[N * LG], rf[N * LG], mn[N * LG], id[N * LG];
inline int Max(const int &x, const int &y) { return x > y ? x : y; }
inline int Min(const int &x, const int &y) { return x < y ? x : y; }
void mdy(int &u, int l, int r, int x, int ad, int dl) {
if(!u) u = ++tot;
if(l >= r) {
if(!id[u]) id[u] = ++cnt;
multiset<int> &s = st[id[u]];
if(ad) s.insert(ad);
if(dl) s.erase(s.find(dl));
mn[u] = s.size() ? *s.begin() : INF; return ;
}
int mid = (l + r) >> 1;
if(x <= mid) mdy(lf[u], l, mid, x, ad, dl);
else mdy(rf[u], mid + 1, r, x, ad, dl);
mn[u] = Min(mn[lf[u]], mn[rf[u]]);
}
void add(Q x) {
multiset<int> &s = pp[x.type];
IT itr = s.upper_bound(x.pos), itl = itr; --itl;
mdy(rt, 0, INF, *itr, x.pos, *itl), mdy(rt, 0, INF, x.pos, *itl, 0);
s.insert(x.pos); if(s.size() == 3) ++clr;
}
void del(Q x) {
multiset<int> &s = pp[x.type]; s.erase(s.find(x.pos));
IT itr = s.upper_bound(x.pos), itl = itr; --itl;
mdy(rt, 0, INF, *itr, *itl, x.pos), mdy(rt, 0, INF, x.pos, 0, *itl);
if(s.size() == 2) --clr;
}
int ask(Q x) {
if(clr < k) return -1;
int l = 0, r = INF, mid, t, tt = INF, u = rt;
for(; l < r;) {
mid = (l + r) >> 1, t = Min(tt, mn[rf[u]]);
if(x.pos <= mid && t + mid >= x.pos * 2)
tt = t, r = mid, u = lf[u];
else u = rf[u], l = mid + 1;
}
return l - x.pos;
}
int main() {
scanf("%d%d%d", &n, &k, &m), mn[0] = INF;
for(int i = 1; i <= k; i++)
pp[i].insert(-INF), pp[i].insert(INF), mdy(rt, 0, INF, INF, -INF, 0);
for(int i = 1, x, t, a, b; i <= n; i++) {
scanf("%d%d%d%d", &x, &t, &a, &b);
q[++len] = Q(1, x, t, a), q[++len] = Q(2, x, t, b + 1);
}
for(int i = 1, x, y; i <= m; i++)
scanf("%d%d", &x, &y), q[++len] = Q(3, x, i, y);
sort(q + 1, q + len + 1);
for(int i = 1; i <= len; i++) {
if(q[i].opt == 1) add(q[i]);
else if(q[i].opt == 2) del(q[i]);
else ans[q[i].type] = ask(q[i]);
}
for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
|