#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
struct query{
int x,t,type;
bool operator <(query b) const{
if(t == b.t){
return type < b.type;
}
return t < b.t;
}
};
vector<ordered_set> segment;
multiset<int> ms[300001];
int n,q,k,t,ans[300001];
vector<query> qs;
vector<int> all;
void del(int curr , int val){
while(curr){
segment[curr].erase(segment[curr].find_by_order(segment[curr].order_of_key(val)));
curr /= 2;
}
}
void add(int curr , int val){
while(curr){
segment[curr].insert(val);
curr /= 2;
}
}
int cmp(int val){
return lower_bound(all.begin(),all.end(),val)-all.begin()+1;
}
int num(int a , int b , int val , int curr , int l , int r){
if(b < l || a > r){
return 0;
}
if(a <= l && b >= r){
return segment[curr].size()-segment[curr].order_of_key(val);
}
int mid = (l+r)/2;
return num(a,b,val,2*curr,l,mid)+num(a,b,val,2*curr+1,mid+1,r);
}
int main(){
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin >> n >> k >> q;
for(int i = 1 ; i <= k ; i += 1){
ms[i].insert(100000001);
}
for(int i = 0 ; i < n ; i += 1){
int x,t,a,b;
cin >> x >> t >> a >> b;
all.push_back(x);
qs.push_back({x,a,t});
qs.push_back({x,b+1,-t});
}
for(int i = 1 ; i <= q ; i += 1){
int l,y;
cin >> l >> y;
all.push_back(l);
qs.push_back({l,y,k+i});
}
assert(false);
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
t = pow(2,ceil(log2(all.size())));
segment.resize(2*t);
sort(qs.begin(),qs.end());
for(auto i : qs){
if(i.type > k){
i.type -= k;
if(num(1,t,t+1,1,1,t) < k){
ans[i.type] = -1;
continue;
}
int first = -1 , last = 100000000;
while(last-first > 1){
int mid = (first+last)/2 , val1 = lower_bound(all.begin(),all.end(),i.x-mid)-all.begin()+1;
int val2 = upper_bound(all.begin(),all.end(),i.x+mid)-all.begin();
if(num(val1,val2,val2+1,1,1,t) >= k){
last = mid;
}else{
first = mid;
}
}
ans[i.type] = last;
}else if(i.type > 0){
i.x = cmp(i.x);
auto it = ms[i.type].lower_bound(i.x);
int val = *it;
add(i.x+t-1,val);
if(it != ms[i.type].begin()){
it--;
int pos = *it;
del(pos+t-1,val) , add(pos+t-1,i.x);
}
ms[i.type].insert(i.x);
}else{
i.x = cmp(i.x);
i.type = -i.type;
ms[i.type].erase(ms[i.type].find(i.x));
auto it = ms[i.type].lower_bound(i.x);
int val = *it;
del(i.x+t-1,val);
if(it != ms[i.type].begin()){
it--;
int pos = *it;
del(pos+t-1,i.x) , add(pos+t-1,val);
}
}
}
for(int i = 1 ; i <= q ; i += 1){
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
29004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
29004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
49316 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
29320 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
68 ms |
49136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
29268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
47432 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
29004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
29004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
