#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 20;
const int inf = 1e9;
set<pair<int,int>> tindex[maxn];
int ans[maxn];
vector<int> cmp;
multiset<int> seg[8*maxn];
pair<int,int> get(int id, int L, int R, int idx){
if (R <= idx or idx < L)
return {inf, 0};
if (L + 1 == R){
if (seg[id].empty())
return {inf,0};
return {*seg[id].begin(), *seg[id].rbegin()};
}
pair<int,int> ret = {inf,0};
if (!seg[id].empty())
ret = {*seg[id].begin(), *seg[id].rbegin()};
int mid = (L + R) >> 1;
auto it1 = get(2*id+0, L, mid, idx);
auto it2 = get(2*id+1, mid, R, idx);
ret.first = min({ret.first, it1.first, it2.first});
ret.second = max({ret.second, it1.second, it2.second});
return ret;
}
void change(int id, int L, int R, int l, int r, int x, char type){
if (r <= L or R <= l)
return;
if (l <= L and R <= r){
if (type == 'A')
seg[id].insert(x);
else
seg[id].erase(seg[id].find(x));
return;
}
int mid = (L + R) >> 1;
change(2*id+0, L, mid, l, r, x, type);
change(2*id+1, mid, R, l, r, x, type);
}
int m;
pair<int,int> getpre(int x, int idx, int type){
auto it = tindex[type].lower_bound(make_pair(x,idx));
assert(it != tindex[type].end());
if (it == tindex[type].begin())
return {-1,-1};
it --;
return *it;
}
pair<int,int> getnex(int x, int idx, int type){
auto it = tindex[type].lower_bound(make_pair(x,idx));
assert(it != tindex[type].end());
it ++;
if (it == tindex[type].end())
return {-1,-1};
return *it;
}
void add(int x, int idx, int type){
if (x == -1)
return;
int pre = getpre(x,idx,type).first, nex = getnex(x,idx,type).first;
if (pre == -1)
pre = 0;
else
pre = lower_bound(cmp.begin(), cmp.end(), (pre+x+1)/2) - cmp.begin();
if (nex == -1)
nex = m;
else
nex = lower_bound(cmp.begin(), cmp.end(), (nex+x+1)/2) - cmp.begin();
change(1, 0, m, pre, nex, x, 'A');
}
void del(int x, int idx, int type){
if (x == -1)
return;
int pre = getpre(x,idx,type).first, nex = getnex(x,idx,type).first;
if (pre == -1)
pre = 0;
else
pre = lower_bound(cmp.begin(), cmp.end(), (pre+x+1)/2) - cmp.begin();
if (nex == -1)
nex = m;
else
nex = lower_bound(cmp.begin(), cmp.end(), (nex+x+1)/2) - cmp.begin();
change(1, 0, m, pre, nex, x, 'D');
}
int main(){
ios_base::sync_with_stdio(false);
int n, k, q;
cin >> n >> k >> q;
vector<pair<pair<int,int>, pair<int,int>>> event;
for (int i = 0; i < n; i++){
int x, t, a, b;
cin >> x >> t >> a >> b;
event.push_back({{a,i}, {x,t}});
event.push_back({{b,n+1+i}, {x,t}});
cmp.push_back(x);
}
for (int i = 0; i < q; i++){
int l, y;
cin >> l >> y;
cmp.push_back(l);
event.push_back({{y,n}, {l,i}});
}
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
m = cmp.size();
for (int i = 0; i < event.size(); i++)
event[i].second.first = lower_bound(cmp.begin(), cmp.end(), event[i].second.first) - cmp.begin();
sort(event.begin(), event.end());
int cnt = 0;
for (auto Q : event){
if (Q.first.second < n){
int x = Q.second.first, type = Q.second.second, idx = Q.first.second;
if (tindex[type].empty())
cnt ++;
tindex[type].insert({x,idx});
auto nex = getnex(x, idx, type), pre = getpre(x, idx, type);
tindex[type].erase({x,idx});
del(pre.first, pre.second, type);
del(nex.first, nex.second, type);
tindex[type].insert({x,idx});
add(x, idx, type);
add(pre.first, pre.second, type);
add(nex.first, nex.second, type);
}
else if (Q.first.second > n){
int x = Q.second.first, type = Q.second.second, idx = Q.first.second - n - 1;
auto nex = getnex(x,idx,type), pre = getpre(x,idx,type);
del(x, idx, type);
del(pre.first, pre.second, type);
del(nex.first, nex.second, type);
tindex[type].erase({x,idx});
if (tindex[type].empty())
cnt --;
add(pre.first, pre.second, type);
add(nex.first, nex.second, type);
}
else{
int x = Q.second.first, idx = Q.second.second;
if (cnt < k){
ans[idx] = -1;
continue;
}
auto it = get(1, 0, m, x);
ans[idx] = max(cmp[x]-cmp[it.first], cmp[it.second]-cmp[x]);
}
}
for (int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < event.size(); i++)
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
127096 KB |
Output is correct |
| 2 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 3 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
127096 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
127096 KB |
Output is correct |
| 2 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 3 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
127096 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5096 ms |
259188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5073 ms |
218076 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
127096 KB |
Output is correct |
| 2 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 3 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
127096 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
127096 KB |
Output is correct |
| 2 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 3 |
Correct |
63 ms |
127096 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
127096 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
