This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const int INF = 1e9+5;
vector<pair<int, pair<int, int>>> ev;
vector<int> cp;
int n, q, k;
int ans[maxn];
int p[maxn], ty[maxn];
int L[maxn], Y[maxn];
multiset<int> st[4*maxn], pos[maxn];
void add_st(int ql, int qr, int val, int l = 0, int r = cp.size()-1, int id = 1){
if(ql > qr)return;
if(cp[l] > qr || cp[r] < ql)return;
if(ql <= cp[l] && cp[r] <= qr)st[id].insert(val);
else {
int mid = (l+r)>>1;
add_st(ql, qr, val, l, mid, id<<1);
add_st(ql, qr, val, mid+1, r, id<<1|1);
}
}
void del_st(int ql, int qr, int val, int l = 0, int r = cp.size()-1, int id = 1){
if(ql > qr)return;
if(cp[l] > qr || cp[r] < ql)return;
if(ql <= cp[l] && cp[r] <= qr)st[id].erase(st[id].find(val));
else {
int mid = (l+r)>>1;
del_st(ql, qr, val, l, mid, id<<1);
del_st(ql, qr, val, mid+1, r, id<<1|1);
}
}
pair<int, int> get(int pos, int l = 0, int r = cp.size()-1, int id = 1){
pair<int, int> re = make_pair(st[id].empty() ? INF : max(*st[id].rbegin() - pos, pos - *st[id].begin()), st[id].size());
if(l < r){
int mid = (l+r)>>1;
pair<int, int> tmp = pos <= cp[mid] ? get(pos, l, mid, id<<1) : get(pos, mid+1, r, id<<1|1);
re.first = max(re.first, tmp.first);
re.second += tmp.second;
}
return re;
}
void add_range(int l, int r){
if(l == -INF)add_st(-INF, r, r);
else if(r == INF)add_st(l+1, INF, l);
else {
int mid = (l+r)/2;
add_st(l+1, mid, l);
add_st(mid+1, r, r);
}
}
void del_range(int l, int r){
if(l == -INF)del_st(-INF, r, r);
else if(r == INF)del_st(l+1, INF, l);
else {
int mid = (l+r)/2;
del_st(l+1, mid, l);
del_st(mid+1, r, r);
}
}
void add(int x, int col){
auto it = pos[col].insert(x);
if(pos[col].size() == 1){
add_range(-INF, x);
add_range(x, INF);
}
else {
if(next(it) == pos[col].end()){
del_range(*prev(it), INF);
add_range(*prev(it), x);
add_range(x, INF);
}
else if(it == pos[col].begin()){
del_range(-INF, *next(it));
add_range(-INF, x);
add_range(x, *next(it));
}
else {
del_range(*prev(it), *next(it));
add_range(*prev(it), *it);
add_range(*it, *next(it));
}
}
}
void del(int x, int col){
auto it = pos[col].erase(pos[col].find(x));
if(pos[col].size() == 0){
del_range(-INF, x);
del_range(x, INF);
}
else {
if(it == pos[col].end()){
del_range(x, INF);
del_range(*prev(it), x);
add_range(*prev(it), INF);
}
else if(it == pos[col].begin()){
del_range(-INF, x);
del_range(x, *it);
add_range(-INF, *it);
}
else {
del_range(x, *it);
del_range(*prev(it), x);
add_range(*prev(it), *it);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> q;
for(int i = 1; i <= n; i++){
int a, b;
cin >> p[i] >> ty[i] >> a >> b;
ev.push_back({a, {0, i}});
ev.push_back({b+1, {1, i}});
}
for(int i = 1; i <= q; i++){
cin >> L[i] >> Y[i];
ev.push_back({Y[i], {2, i}});
cp.push_back(L[i]);
}
sort(cp.begin(), cp.end());
cp.erase(unique(cp.begin(), cp.end()), cp.end());
sort(ev.begin(), ev.end());
for(auto ele: ev){
pair<int, int> event = ele.second;
if(event.first == 0)add(p[event.second], ty[event.second]);
else if(event.first == 1)del(p[event.second], ty[event.second]);
else {
pair<int, int> tmp = get(L[event.second]);
ans[event.second] = tmp.second == k ? tmp.first : -1;
}
}
for(int i = 1; i <= q; i++)cout << ans[i] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |