#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif // DEBUG
const ll maxn=2e5+5;
const ll inf=1e15;
const ll mod=1e9+7;
vector<tuple<ll,ll,ll>> v;
vector<tuple<ll,ll,ll>> q; //position, l, r
vector<ll> pos;
struct node{
ll s,e,m,val;
node *l,*r;
node (ll _s, ll _e){
s=_s,e=_e,m=(s+e)>>1,val=0;
if (s!=e) l=new node(s,m),r=new node(m+1,e);
}
void upd(ll x, ll v){
if (s==e){
val+=v;
return;
}
if (x>m) r->upd(x,v);
else l->upd(x,v);
val=l->val+r->val;
}
ll query(ll x, ll y){
if (x<=s && e<=y) return val;
if (x>m) return r->query(x,y);
if (y<=m) return l->query(x,y);
return l->query(x,y)+r->query(x,y);
}
}*root;
ll n,k;
void solve(){
vector<tuple<ll,ll,ll,ll>> q2;
//l, position, r, idx
root=new node(0,n);
for (int i=0;i<q.size();i++){
ll b,c,d;
tie(b,c,d)=q[i];
if (c==d-1) return;
ll m=(c+d)>>1;
ll lb=lower_bound(pos.begin(),pos.end(),b-m)-pos.begin();
ll ub=upper_bound(pos.begin(),pos.end(),b+m)-pos.begin()-1;
q2.emplace_back(ub,lb,i,m);
}
sort(q2.begin(),q2.end());
//sort by increasing right endpoint, query towards left
ll ptr=0;
for (auto [ub,lb,i,m]:q2){
while (ptr!=v.size() && get<0>(v[ptr])<=ub){
root->upd(get<1>(v[ptr]),get<2>(v[ptr]));
ptr++;
}
ll a,b,c;
tie(a,b,c)=q[i];
ll res=root->query(lb,ub);
if (res==k) q[i]={a,b,m};
else q[i]={a,m,c};
}
}
map<ll,vector<ll>> m;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll qu,x,t,a,b;
cin>>n>>k>>qu;
for (int i=1;i<=n;i++){
cin>>x>>t>>a>>b;
pos.emplace_back(x);
m[t].emplace_back(x);
}
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
for (auto [u,v1]:m){
sort(v1.begin(),v1.end());
for (int i=0;i<v1.size();i++){
cerr<<u<<' '<<v1[i]<<endl;
v1[i]=lower_bound(pos.begin(),pos.end(),v1[i])-pos.begin();
if (i!=0){
v.emplace_back(v1[i],v1[i-1],-1);
//erase prev
}
v.emplace_back(v1[i],v1[i],1);
//new guy
}
}
sort(v.begin(),v.end());
for (auto [a,b,c]:v) cerr<<a<<' '<<b<<' '<<c<<endl;
for (int i=1;i<=qu;i++){
cin>>x>>t;
q.emplace_back(x,-1,mod); //r is can
}
for (int i=1;i<=28;i++){
solve();
}
for (auto u:q){
ll res=get<2>(u);
if (res>100'000'000) cout<<-1<<endl;
else cout<<res<<endl;
}
return 0;
}
Compilation message
new_home.cpp: In function 'void solve()':
new_home.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i=0;i<q.size();i++){
| ~^~~~~~~~~
new_home.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | while (ptr!=v.size() && get<0>(v[ptr])<=ub){
| ~~~^~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i=0;i<v1.size();i++){
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5070 ms |
968692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5086 ms |
897184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
