#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
#define rand() (1ll * rand() * rand() + rand() + 1)
struct Node{
int left = 0, right = 0;
int mx = -INF, val = -INF;
int key = 0, prior = 0;
bool operator<(Node& A){
return key < A.key || (key == A.key && val < A.val);
}
} node[2000000];
int new_node(int k, int v){
static int ind = 1;
node[ind].key = k;
node[ind].val = node[ind].mx = v;
node[ind].prior = rand();
return ind++;
}
struct Treap{
int root = 0;
void up(int j){
if(!j)return;
int l = node[j].left, r = node[j].right;
node[j].mx = max(node[j].val, max(node[l].mx, node[r].mx));
}
void split(int j, Node& v, int& l, int& r){
if(!j) l = r = 0;
else if(node[j] < v) split(node[j].right, v, node[j].right, r), l = j;
else split(node[j].left, v, l, node[j].left), r = j;
up(j);
}
void merge(int& j, int l, int r){
if(!l || !r) j = max(l, r);
else if(node[l].prior > node[r].prior) merge(node[l].right, node[l].right, r), j = l;
else merge(node[r].left, l, node[r].left), j = r;
up(j);
}
void insert(int& j, int i){
if(!j) j = i;
else if(node[i].prior > node[j].prior) split(j, node[i], node[i].left, node[i].right), j = i;
else{
if(node[i] < node[j]) insert(node[j].left, i);
else insert(node[j].right, i);
}
up(j);
}
void erase(int& j, Node& v){
assert(j);
if(node[j].key == v.key && node[j].val == v.val) merge(j, node[j].left, node[j].right);
else if(v < node[j]) erase(node[j].left, v);
else erase(node[j].right, v);
up(j);
}
void add(int k, int v){
insert(root, new_node(k, v));
}
void remove(int k, int v){
erase(root, node[new_node(k, v)]);
}
int query(int x, int y){
int a, b, c;
Node t; t.key = x; t.val = -INF;
split(root, t, a, b);
t.key = y, t.val = INF;
split(b, t, b, c);
int ret = node[b].mx;
merge(root, a, b);
merge(root, root, c);
return ret;
}
} Ltree, Rtree;
struct Store{
int x, type, tl, tr;
};
struct Query{
int x, time, id;
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
srand(time(NULL));
int n, k, q;
cin >> n >> k >> q;
vector<Store> X, Y;
vector<Query> Q;
vector<int> ans(q);
vector<int> cnt(k + 1, 0);
multiset<int> K[k + 1];
int c = k;
for(int i = 1; i <= k; i++) {
K[i].insert(-2e9), K[i].insert(2e9);
Rtree.add(0, 2e9);
Ltree.add(0, 2e9);
}
for(int i = 0; i < n; i++){
int a, b, c, d;
cin >> a >> b >> c >> d; a*=2;
X.pb({a, b, c, d});
Y.pb({a, b, c, d});
}
for(int i = 0; i < q; i++){
int a, b;
cin >> a >> b; a*=2;
Q.pb({a, b, i});
}
sort(all(X), [&](Store& A, Store& B){return A.tl < B.tl;});
sort(all(Y), [&](Store& A, Store& B){return A.tr < B.tr;});
sort(all(Q), [&](Query& A, Query& B){return A.time < B.time;});
int a = 0, b = 0;
for(auto& curr : Q){
while(a < n && X[a].tl <= curr.time){
int t = X[a].type, x = X[a].x;
if(++cnt[t] == 1) c--;
auto next = K[t].upper_bound(x);
auto prev = std::prev(next);
int mid = (*next + *prev) / 2;
Rtree.remove(mid, -*prev);
Ltree.remove(mid, *next);
mid = (*prev + x) / 2;
Rtree.add(mid, -*prev);
Ltree.add(mid, x);
mid = (x + *next) / 2;
Rtree.add(mid, -x);
Ltree.add(mid, *next);
K[t].insert(x);
a++;
}
while(b < n && Y[b].tr < curr.time){
int t = Y[b].type, x = Y[b].x;
if(--cnt[Y[b].type] == 0) c++;
K[t].erase(K[t].find(x));
auto next = K[t].upper_bound(x);
auto prev = std::prev(next);
int mid = (*prev + x) / 2;
Rtree.remove(mid, -*prev);
Ltree.remove(mid, x);
mid = (x + *next) / 2;
Rtree.remove(mid, -x);
Ltree.remove(mid, *next);
mid = (*next + *prev) / 2;
Rtree.add(mid, -*prev);
Ltree.add(mid, *next);
b++;
}
if(c > 0){
ans[curr.id] = -2;
continue;
}
ans[curr.id] = max(Rtree.query(curr.x, INF) + curr.x, Ltree.query(-INF, curr.x) - curr.x);
}
for(int i = 0; i < q; i++) cout << ans[i] / 2 << ' ';
}
Compilation message
Compilation timeout while compiling new_home
