#include "bits/stdc++.h"
using namespace std;
#define ar array
const int MX = 1e8 + 5;
const int N = 3e5 + 5;
const int M = 9e5 + 5;
struct BIT{
multiset<int> tree[M];
void add(int i, int r){
//~ if(!i){
//~ cout<<i<<endl;
//~ }
for(;i<M;i+=(i&-i)) tree[i].insert(r);
}
void del(int i, int r){
//~ if(!i){
//~ cout<<i<<endl;
//~ }
for(;i<M;i+=(i&-i)) tree[i].erase(tree[i].lower_bound(r));
}
int get(int i){
int r=0;
for(;i>0;i-=(i&-i)){
if(!tree[i].empty()) r = max(r, *tree[i].rbegin());
} return r;
}
}tree;
int x[N], t[N], a[N], b[N];
int l[N], y[N];
multiset<int> ss[N];
/*
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
*/
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q; cin>>n>>k>>q;
for(int i=0;i<n;i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
t[i]--, b[i]++;
}
for(int i=0;i<q;i++){
cin>>l[i]>>y[i];
}
vector<int> in(n); iota(in.begin(), in.end(), 0);
vector<int> out(n); iota(out.begin(), out.end(), 0);
vector<int> p(q); iota(p.begin(), p.end(), 0);
sort(in.begin(), in.end(), [&](int i, int j){
return (a[i] < a[j]);
});
sort(out.begin(), out.end(), [&](int i, int j){
return (b[i] < b[j]);
});
sort(p.begin(), p.end(), [&](int i, int j){
return (y[i] < y[j]);
});
vector<int> tot = {0, MX};
for(int i=0;i<n;i++) tot.push_back(x[i]);
{
int c = k;
auto cret = [&](int i){
auto it = ss[t[i]].upper_bound(x[i]);
if(ss[t[i]].empty()) c--;
if(it == ss[t[i]].end()){
if(it != ss[t[i]].begin()){
it--;
tot.push_back((*it + x[i]) >> 1);
}
} else {
if(it == ss[t[i]].begin()){
tot.push_back((x[i] + *it) >> 1);
} else {
auto R = it; it--;
tot.push_back((*it + x[i]) >> 1);
tot.push_back((x[i] + *R) >> 1);
}
}
ss[t[i]].insert(x[i]);
};
auto ecrt = [&](int i){
ss[t[i]].erase(ss[t[i]].find(x[i]));
if(ss[t[i]].empty()) c++;
auto it = ss[t[i]].upper_bound(x[i]);
if(it != ss[t[i]].end()){
if(it != ss[t[i]].begin()){
auto R = it; it--;
tot.push_back((*it + *R) >> 1);
}
}
};
int I = 0, O = 0;
for(auto i : p){
while(I < n && a[in[I]] <= y[i]){
//~ In(in[I++]);
cret(in[I++]);
}
while(O < n && b[out[O]] <= y[i]){
//~ Out(out[O++]);
ecrt(out[O++]);
}
}
while(I < n) cret(in[I++]);
while(O < n) ecrt(out[O++]);
}
sort(tot.begin(), tot.end());
tot.erase(unique(tot.begin(), tot.end()), tot.end());
vector<int> res(q, -1);
auto solve = [&](){
int I = 0, O = 0, c = k;
auto add = [&](int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
m = upper_bound(tot.begin(), tot.end(), m) - tot.begin();
tree.add(m, r);
//~ cout<<l<<" "<<m<<"\n";
}; auto dec = [&](int x) {
tree.add(1, x);
//~ cout<<1<<" "<<x<<"\n";
};
auto dadd = [&](int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
m = upper_bound(tot.begin(), tot.end(), m) - tot.begin();
tree.del(m, r);
//~ cout<<l<<" "<<m<<"\n";
}; auto ddec = [&](int x) {
tree.del(1, x);
};
auto In = [&](int i){
auto it = ss[t[i]].upper_bound(x[i]);
if(ss[t[i]].empty()) c--;
if(it == ss[t[i]].end()){
if(it != ss[t[i]].begin()){
it--;
//~ dinc(*it);
add(*it, x[i]);
//~ inc(x[i]);
} else {
//~ inc(x[i]);
dec(x[i]);
}
} else {
if(it == ss[t[i]].begin()){
ddec(*it);
add(x[i], *it);
dec(x[i]);
} else {
auto R = it; it--;
dadd(*it, *R);
add(*it, x[i]);
add(x[i], *R);
}
}
ss[t[i]].insert(x[i]);
};
auto Out = [&](int i){
ss[t[i]].erase(ss[t[i]].find(x[i]));
if(ss[t[i]].empty()) c++;
auto it = ss[t[i]].upper_bound(x[i]);
if(it == ss[t[i]].end()){
if(it == ss[t[i]].begin()){
//~ dinc(x[i]);
ddec(x[i]);
} else {
it--;
dadd(*it, x[i]);
//~ dinc(x[i]);
//~ inc(*it);
}
} else {
if(it == ss[t[i]].begin()){
dadd(x[i], *it);
ddec(x[i]);
dec(*it);
} else {
auto R = it; it--;
dadd(*it, x[i]);
dadd(x[i], *R);
add(*it, *R);
}
}
};
for(auto i : p){
while(I < n && a[in[I]] <= y[i]){
//~ In(in[I++]);
In(in[I++]);
}
while(O < n && b[out[O]] <= y[i]){
//~ Out(out[O++]);
Out(out[O++]);
}
int P = upper_bound(tot.begin(), tot.end(), l[i]) - tot.begin();
//~ cout<<P<<"\n";
if(!c) res[i] = max(res[i], tree.get(P) - l[i]);
}
while(I < n) In(in[I++]);
while(O < n) Out(out[O++]);
};
assert((int)tot.size() < M);
solve();
for(int i=0;i<n;i++) x[i] = MX - x[i];
for(int i=0;i<q;i++) l[i] = MX - l[i];
for(auto& x : tot) x = MX - x;
reverse(tot.begin(), tot.end());
solve();
//~ cout<<"here"<<endl;
for(int i=0;i<q;i++){
cout<<res[i]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
56652 KB |
Output is correct |
| 2 |
Correct |
28 ms |
56692 KB |
Output is correct |
| 3 |
Correct |
29 ms |
56668 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
56700 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
56652 KB |
Output is correct |
| 2 |
Correct |
28 ms |
56692 KB |
Output is correct |
| 3 |
Correct |
29 ms |
56668 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
56700 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5049 ms |
259788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
835 ms |
173928 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
56652 KB |
Output is correct |
| 2 |
Correct |
28 ms |
56692 KB |
Output is correct |
| 3 |
Correct |
29 ms |
56668 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
56700 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
56652 KB |
Output is correct |
| 2 |
Correct |
28 ms |
56692 KB |
Output is correct |
| 3 |
Correct |
29 ms |
56668 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
56700 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
