//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> super_set;
#define endl '\n'
const int DIM = 3E5+7;
const int SZ = 407;
const int INF = 1E9+7;
set<pair<int,int> > K[SZ];
struct node{
int t,x,type,pos;
};
bool mc(node &a,node &b){
if (a.t==b.t)
if (abs(a.type)==abs(b.type))
return a.type<b.type;
else
return (a.type==0)<(b.type==0);
return a.t<b.t;
}
int ans[DIM];
int n,q,k;
int solve(){
vector<node> events;
for(int i = 1;i<=n;++i){
int x,t,l,r;
cin>>x>>t>>l>>r;
events.push_back({l,x,t,i});
events.push_back({r+1,x,t,-i});
}
for(int i = 1;i<=q;++i){
int x,t;
cin>>x>>t;
events.push_back({t,x,0,i});
}
sort(events.begin(),events.end(),mc);
for(auto to:events){
if (to.type==0){
int dist = 0;
for(int i = 1;i<=k;++i){
int d = INF;
auto lb = K[i].lower_bound({to.x,INF});
if (lb!=K[i].begin()){
lb = prev(lb);
d = min(d,to.x-lb->first);
}
auto rb = K[i].lower_bound({to.x,0});
if (rb!=K[i].end()){
d = min(d,rb->first-to.x);
}
dist = max(dist,d);
}
if (dist==INF)
ans[to.pos] = -1;
else ans[to.pos] = dist;
}
else{
if (to.pos<0)
K[to.type].erase({to.x,-to.pos});
else K[to.type].insert({to.x,to.pos});
}
}
for(int i = 1;i<=q;++i)
cout<<ans[i]<<endl;
return 1;
}
vector<int> V[DIM];
super_set S;
int get(int l,int r){
return S.order_of_key({r,INF})-S.order_of_key({l-1,INF});
}
int solve1(){
for(int i = 1;i<=n;++i){
int x,t,a,b;
cin>>x>>t>>a>>b;
V[t].push_back(x);
}
vector<node> events;
for(int i = 1;i<=k;++i){
sort(V[i].begin(),V[i].end());
for(int j = 0;j<V[i].size();++j){
int prev = j==0?-INF:V[i][j-1],next = j==V[i].size()-1?INF:V[i][j+1];
int l = max(0,(V[i][j]+prev)/2);
int r = min(int(1E9),(V[i][j]+next)/2);
events.push_back({l,V[i][j],i,0});
events.push_back({r,V[i][j],-i,0});
}
}
for(int i = 1;i<=q;++i){
int x,t;
cin>>x>>t;
events.push_back({t,x,0,i});
}
sort(events.begin(),events.end(),mc);
for(auto to:events){
if (to.type==0){
int l = 0,r = 1E9;
while(l!=r){
int tm = (l+r)/2;
if (get(to.x-tm,to.x+tm)==k)
r = tm;
else l = tm+1;
}
if (l==1E9)
ans[to.pos] = -1;
else ans[to.pos] = l;
}
else{
if (to.type<0)
S.erase({to.x,-to.type});
else S.insert({to.x,to.type});
}
}
for(int i = 1;i<=q;++i)
cout<<ans[i]<<endl;
return 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>q;
if (k<=0)
solve();
else
solve1();
return 0;
}
Compilation message
new_home.cpp: In function 'bool mc(node&, node&)':
new_home.cpp:18:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
18 | if (a.t==b.t)
| ^
new_home.cpp: In function 'int solve1()':
new_home.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j = 0;j<V[i].size();++j){
| ~^~~~~~~~~~~~
new_home.cpp:88:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | int prev = j==0?-INF:V[i][j-1],next = j==V[i].size()-1?INF:V[i][j+1];
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1634 ms |
31976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1149 ms |
27448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7372 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
