// In the name of God
// We are everywhere while we are nowhere(Haj NEZAM...)
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define lc 2 * v
#define nt(v) v ^ 1
#define rc 2 * v + 1
#define PB push_back
#define MP make_pair
#define ll long long
// #define int long long
#define ld long double
#define mid (s + e) / 2
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define pll pair <long long , long long>
#define piii pair <int , pair <int , int> >
#define FAST ios::sync_with_stdio(0);cin.tie(0)
#define UNI(e) e.resize(unique(_all(e)) - e.begin())
#define kill(e) cout << e << '\n'
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,avx")
#pragma GCC optimize("O3,unroll-loops")
const int maxn = 9e5 + 5 , N = 400 + 5 , SQ = 55 , base = 879169 , mod = 1e9 + 7 , INF = 1e9 + 5 , lg = 11;
const ld eps = 1e-6;
struct node {
int mnL = INF , mxR = -INF;
};
node seg[4 * maxn];
int x[maxn] , t[maxn] , a[maxn] , b[maxn] , ql[maxn] , qx[maxn];
int n , k , q , SZ , cnt_zero , res[maxn] , L[maxn] , R[maxn];
set <pii> active[maxn];
vector <int> vec[maxn];
vector <int> add[maxn];
vector <int> rem[maxn];
vector <piii> comp1;
vector <int> comp2;
void compress() {
sort(_all(comp1)) , sort(_all(comp2)); UNI(comp2);
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(_all(comp2) , a[i]) - comp2.begin();
b[i] = lower_bound(_all(comp2) , b[i]) - comp2.begin();
add[a[i]].PB(i) , rem[b[i]].PB(i);
}
for (int i = 0; i < q; ++i) {
ql[i] = lower_bound(_all(comp2) , ql[i]) - comp2.begin();
vec[ql[i]].PB(i);
}
for (int i = 0; i < n + q; ++i) {
if(!comp1[i].S.F) x[comp1[i].S.S] = i;
else qx[comp1[i].S.S] = i;
}
}
void modify_L(int p , int r , int v = 1 , int s = 0 , int e = SZ) {
if(e - s == 1) {
seg[v].mnL = L[s] = r;
return ;
}
if(p < mid) modify_L(p , r , lc , s , mid);
else modify_L(p , r , rc , mid , e);
seg[v].mnL = min(seg[lc].mnL , seg[rc].mnL);
}
void modify_R(int p , int r , int v = 1 , int s = 0 , int e = SZ) {
if(e - s == 1) {
seg[v].mxR = R[s] = r;
return ;
}
if(p < mid) modify_R(p , r , lc , s , mid);
else modify_R(p , r , rc , mid , e);
seg[v].mxR = max(seg[lc].mxR , seg[rc].mxR);
}
int get_L(int l , int r , int p , int v = 1 , int s = 0 , int e = SZ) {
if(l >= e || s >= r || seg[v].mnL >= p) return -1;
if(e - s == 1) return s;
int res = get_L(l , r , p , rc , mid , e);
return (res != -1 ? res : get_L(l , r , p , lc , s , mid));
}
int get_R(int l , int r , int p , int v = 1 , int s = 0 , int e = SZ) {
if(l >= e || s >= r || seg[v].mxR <= p) return -1;
if(e - s == 1) return s;
int res = get_R(l , r , p , lc , s , mid);
return (res != -1 ? res : get_R(l , r , p , rc , mid , e));
}
void add_store(int st) {
// cout << "ADD STORE " << st << ' ' << x[st] << endl;
if(!_sz(active[t[st]])) cnt_zero--;
set <pii> ::iterator it = active[t[st]].lower_bound({x[st] , -1});
R[x[st]] = (it != active[t[st]].end() ? it -> F : maxn);
L[x[st]] = (it != active[t[st]].begin() ? (--it) -> F : -1);
active[t[st]].insert({x[st] , st});
modify_L(x[st] , L[x[st]]) , modify_R(x[st] , R[x[st]]);
if(R[x[st]] != maxn) modify_L(R[x[st]] , x[st]);
if(L[x[st]] != -1) modify_R(L[x[st]] , x[st]);
}
void rem_store(int st) {
// cout << "REM STORE " << st << ' ' << x[st] << endl;
// cout << "good" << endl;
if(R[x[st]] != maxn) modify_L(R[x[st]] , L[x[st]]);
// cout << "GOOZ" << endl;
if(L[x[st]] != -1) modify_R(L[x[st]] , R[x[st]]);
// cout << "HEY" << endl;
modify_L(x[st] , INF) , modify_R(x[st] , -INF);
active[t[st]].erase({x[st] , st});
// cout << "HOY" << endl;
if(!_sz(active[t[st]])) cnt_zero++;
}
int32_t main() {
FAST;
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> t[i] >> a[i] >> b[i];
comp1.PB({x[i] , {0 , i}}) , comp2.PB(a[i]) , comp2.PB(b[i]);
}
for (int i = 0; i < q; ++i) {
cin >> qx[i] >> ql[i];
comp1.PB({qx[i] , {1 , i}}) , comp2.PB(ql[i]);
}
compress();
cnt_zero = k;
SZ = _sz(comp1);
fill(L , L + maxn , -1);
fill(R , R + maxn , maxn);
// cout << SZ << endl;
for (int i = 0; i < maxn; ++i) {
for (auto st : add[i]) add_store(st);
for (auto qu : vec[i]) {
if(cnt_zero) {
res[qu] = -1; continue;
}
// cout << qu << ' ' << qx[qu] << ' ' << R[0] << ' ' << L[3] << endl;
int pos1 = get_R(0 , qx[qu] + 1 , qx[qu]);
int pos2 = get_L(qx[qu] , SZ , qx[qu]);
int val1 = (pos1 == -1 ? INF : comp1[pos1].F);
int val2 = (pos2 == -1 ? -INF : comp1[pos2].F);
// cout << pos1 << ' ' << pos2 << ' ' << val1 << ' ' << val2 << endl;
res[qu] = max(comp1[qx[qu]].F - val1 , val2 - comp1[qx[qu]].F);
}
for (auto st : rem[i]) rem_store(st);
}
for (int i = 0; i < q; ++i) {
cout << res[i] << '\n';
}
}
Compilation message
Compilation timeout while compiling new_home
