#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
const ll maxn = 3e5 + 17 , inf = 1e10;
pll operator + (pll a , pll b){
pll res;
res.first = a.first + b.first;
res.second = a.second + b.second;
return res;
}
void operator += (pll &a , pll b){
a = a + b;
return;
}
vector<ll> v;
struct segtree {
ll sz = 1;
pll def = {0 , 0};
vector<set<pll>> van;
vector<set<pll , greater<pll>>> vax;
set<pll> sn;
set<pll , greater<pll>> sx;
void init(ll n){
while(sz < n) sz <<= 1;
sn.insert({inf , -1});
sx.insert({-inf , -1});
van.assign(sz << 1 , sn);
vax.assign(sz << 1 , sx);
return;
}
void add(ll l , ll r , pll k , bool c , ll x , ll lx , ll rx){
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
if(c){
vax[x].insert(k);
} else {
van[x].insert(k);
// cout<<(*van[x].begin()).first<<' '<<k.first<<"f\n";
}
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
add(l , r , k , c , ln , lx , m); add(l , r , k , c , rn , m , rx);
return;
}
void add(ll l , ll r , pll k , bool c){
ll lv = upper_bound(all(v) , l) - v.begin() - 1 , rv = lower_bound(all(v) , r) - v.begin();
// cout<<l<<' '<<r<<" --- ";
// cout<<lv<<' '<<rv<<'\n';
// cout<<v[4]<<'\n';
if(lv == rv) return;
add(lv , rv , k , c , 0 , 0 , sz);
return;
}
void del(ll l , ll r , pll k , bool c , ll x , ll lx , ll rx){
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
if(c){
vax[x].erase(k);
} else {
van[x].erase(k);
}
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
del(l , r , k , c , ln , lx , m); del(l , r , k , c , rn , m , rx);
return;
}
void del(ll l , ll r , pll k , bool c){
ll lv = upper_bound(all(v) , l) - v.begin() - 1 , rv = lower_bound(all(v) , r) - v.begin();
if(lv == rv) return;
del(lv , rv , k , c , 0 , 0 , sz);
return;
}
pll cal(ll i , ll x , ll lx , ll rx){
if(rx - lx == 1){
ll h = (*vax[x].begin()).first , o = (*van[x].begin()).first;
return {o , h};
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
pll a;
if(i < m){
a = cal(i , ln , lx , m);
} else {
a = cal(i , rn , m , rx);
}
ll h = max((*vax[x].begin()).first , a.second) , o = min((*van[x].begin()).first , a.first);
return {o , h};
}
pll cal(ll i){
ll iv = lower_bound(all(v) , i) - v.begin();
return cal(iv , 0 , 0 , sz);
}
};
segtree st;
ll l[maxn] , r[maxn] , x[maxn] , c[maxn] , y[maxn] , t[maxn] , ans[maxn] , cnt[maxn];
set<pll> s[maxn] , cs;
vector<ll> vt , dl[maxn] , ad[maxn] , qu[maxn];
void add(ll i){
cs.erase({cnt[c[i]]++ , c[i]});
cs.insert({cnt[c[i]] , c[i]});
// cout<<i<<' '<<c[i]<<' '<<cnt[c[i]]<<'\n';
s[c[i]].insert({x[i] , i});
auto it = s[c[i]].lower_bound({x[i] , i});
ll pr , nx;
pll p , n;
it++;
n = *it;
nx = (*it).first;
it--; it--;
p = *it;
pr = (*it).first;
ll mp = (pr + x[i] + 1) / 2 , mn = (x[i] + nx + 1) / 2 , m = (pr + nx + 1) / 2;
pll r = {x[i] , i};
st.del(pr , m , p , 0);
st.del(m , nx , n , 1);
if(p.first != -inf) st.add(pr , mp , p , 0);
st.add(mp , x[i] , r , 1);
st.add(x[i] , mn , r , 0);
// cout<<mp<<' '<<x[i]<<' '<<mn<<'\n';
if(n.first != inf) st.add(mn , nx , n , 1);
return;
}
void del(ll i){
// cout<<"del "<<i<<' '<<c[i]<<'\n';
cs.erase({cnt[c[i]]-- , c[i]});
cs.insert({cnt[c[i]] , c[i]});
auto it = s[c[i]].lower_bound({x[i] , i});
ll pr , nx;
pll p , n;
it++;
n = *it;
nx = (*it).first;
it--; it--;
p = *it;
pr = (*it).second;
s[c[i]].erase({x[i] , i});
ll m = (nx + pr + 1) / 2 , mp = (pr + x[i] + 1) / 2 , mn = (x[i] + nx + 1) / 2;
pll r = {x[i] , i};
st.del(pr , mp , p , 0);
st.del(mp , x[i] , r , 1);
st.del(x[i] , mn , r , 0);
st.del(mn , nx , n , 1);
if(p.first != -inf) st.add(pr , m , p , 0);
if(n.first != inf) st.add(m , nx , n , 1);
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n , k , q;
cin>>n>>k>>q;
for(ll i = 0 ; i < n ; i++){
cin>>x[i]>>c[i]>>l[i]>>r[i]; r[i]++; c[i]--;
v.push_back(x[i]);
vt.push_back(l[i]); vt.push_back(r[i]);
}
for(ll i = 0 ; i < q ; i++){
cin>>y[i]>>t[i];
v.push_back(y[i]);
vt.push_back(t[i]);
}
sort(all(v));
v.resize(distance(v.begin() , unique(all(v))));
// for(auto i : v){
// cout<<i<<' ';
// }
// cout<<'\n';
ll vs = sze(v);
st.init(vs);
for(ll i = 0 ; i < k ; i++){
s[i].insert({-inf , -1}); s[i].insert({inf , -1});
}
sort(all(vt));
vt.resize(distance(vt.begin() , unique(all(vt))));
for(ll i = 0 ; i < n ; i++){
l[i] = lower_bound(all(vt) , l[i]) - vt.begin();
ad[l[i]].push_back(i);
r[i] = lower_bound(all(vt) , r[i]) - vt.begin();
dl[r[i]].push_back(i);
}
for(ll i = 0 ; i < q ; i++){
t[i] = lower_bound(all(vt) , t[i]) - vt.begin();
qu[t[i]].push_back(i);
}
ll ts = sze(vt);
for(ll i = 0 ; i < k ; i++){
cs.insert({0 , i});
}
for(ll i = 0 ; i < ts ; i++){
for(auto j : ad[i]){
add(j);
}
for(auto j : dl[i]){
del(j);
}
for(auto j : qu[i]){
if((*(cs.begin())).first == 0){
ans[j] = -1;
continue;
}
pll h = st.cal(y[j]);
ans[j] = max(y[j] - h.first , h.second - y[j]);
}
}
for(ll i = 0 ; i < q ; i++){
cout<<ans[i]<<'\n';
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/
/*
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
*/
/*
1 1 1
100000000 1 1 1
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
17 ms |
35584 KB |
Output is correct |
| 3 |
Correct |
18 ms |
35556 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
35540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
17 ms |
35584 KB |
Output is correct |
| 3 |
Correct |
18 ms |
35556 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
35540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5105 ms |
811384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1083 ms |
994456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
17 ms |
35584 KB |
Output is correct |
| 3 |
Correct |
18 ms |
35556 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
35540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
17 ms |
35584 KB |
Output is correct |
| 3 |
Correct |
18 ms |
35556 KB |
Output is correct |
| 4 |
Incorrect |
17 ms |
35540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
