#include <bits/stdc++.h>
using namespace std;
struct store
{
int x,t,a,b;
store() {}
store(int _x,int _t,int _a,int _b)
{
x=_x;
t=_t;
a=_a;
b=_b;
}
};
struct hour
{
int x,t,h,p;
hour() {}
hour(int _x,int _t,int _h,int _p)
{
x=_x;
t=_t;
h=_h;
p=_p;
}
};
int n,q,k;
store a[300001];
multiset<int> s[300001];
vector<hour> v;
bool cmp(hour h1,hour h2)
{
if(h1.h==h2.h)return h1.p<h2.p;
return h1.h<h2.h;
}
int x[300001],y[300001];
void read()
{
cin>>n>>k>>q;
for(int i=1; i<=n; i++)
{
cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b;
v.push_back({a[i].x,a[i].t,a[i].a,1});
v.push_back({a[i].x,a[i].t,a[i].b,3});
}
for(int i=1; i<=q; i++)
{
int x[i],y[i];
cin>>x[i]>>y[i];
v.push_back({x[i],i,y[i],2});
}
sort(v.begin(),v.end(),cmp);
}
int ans[300001];
void solve()
{
for(int i=0; i<v.size(); i++)
{
hour h=v[i];
//cout<<h.x<<" "<<h.t<<" "<<h.p<<" "<<h.h<<endl;
if(h.p==1)s[h.t].insert(h.x);
else if(h.p==3)s[h.t].erase(s[h.t].find(h.x));
else
{
int maxx=0;
for(int j=1; j<=k; j++)
{
if(s[j].size()==0)
{
maxx=-1;
break;
}
else
{
auto it=s[j].end();it--;
//cout<<"! "<<j<<" "<<*it<<endl;
if(h.x>=*it)maxx=max(maxx,h.x-*it);
else
{
it=s[j].lower_bound(h.x);
int d=*it-h.x;
//cout<<"! "<<j<<" "<<*it<<" "<<h.x<<endl;
if(it!=s[j].begin())
{
it--;
d=min(d,h.x-*it);
}
maxx=max(maxx,d);
}
}
}
ans[h.t]=maxx;
}
}
for(int i=1; i<=q; i++)
cout<<ans[i]<<endl;
}
int last[300001];
set<int> act;
struct position
{
int x,t;
position(){}
position(int _x,int _t)
{
x=_x;
t=_t;
}
};
bool cmp2(position p1,position p2)
{
return p1.x<p2.x;
}
void subt()
{
vector<position> p;
for(int i=1;i<=n;i++)
{
p.push_back({a[i].x,a[i].t});
}
for(int i=1;i<=q;i++)
{
p.push_back({x[i],-i});
}
sort(p.begin(),p.end(),cmp2);
for(int i=0;i<p.size();i++)
{
if(p[i].t<0)
{
int id=p[i].t;
if(act.size()==0)ans[id]=-1;
else
{
auto it=act.end();
it--;
ans[id]=p[i].x-*it;
}
}
else
{
if(last[p[i].t])act.erase(last[p[i].t]);
last[p[i].t]=p[i].x;
act.insert(p[i].x);
}
}
for(int i=1;i<=k;i++)
last[i]=-1;
for(int i=p.size()-1;i>=0;i--)
{
if(p[i].t<0)
{
int id=p[i].t;
if(act.size()==0)ans[id]=-1;
else
{
auto it=act.begin();
if(ans[id]==-1||ans[id]>*it-p[i].x)
ans[id]=p[i].x-*it;
}
}
else
{
if(last[p[i].t])act.erase(last[p[i].t]);
last[p[i].t]=p[i].x;
act.insert(p[i].x);
}
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<endl;
}
int main()
{
read();
if(n<=6*10000)solve();
else subt();
return 0;
}
/*
4 2 1
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
9 4
*/
Compilation message
new_home.cpp: In function 'void solve()':
new_home.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<hour>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0; i<v.size(); i++)
| ~^~~~~~~~~
new_home.cpp: In function 'void subt()':
new_home.cpp:146:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<position>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i=0;i<p.size();i++)
| ~^~~~~~~~~
new_home.cpp:180:26: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
180 | if(ans[id]==-1||ans[id]>*it-p[i].x)
| ~~~~~~^
new_home.cpp:63:5: note: while referencing 'ans'
63 | int ans[300001];
| ^~~
new_home.cpp:181:27: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
181 | ans[id]=p[i].x-*it;
| ~~~~~~^
new_home.cpp:63:5: note: while referencing 'ans'
63 | int ans[300001];
| ^~~
new_home.cpp:176:36: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
176 | if(act.size()==0)ans[id]=-1;
| ~~~~~~^
new_home.cpp:63:5: note: while referencing 'ans'
63 | int ans[300001];
| ^~~
new_home.cpp:157:23: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
157 | ans[id]=p[i].x-*it;
| ~~~~~~^
new_home.cpp:63:5: note: while referencing 'ans'
63 | int ans[300001];
| ^~~
new_home.cpp:151:36: warning: array subscript -1 is below array bounds of 'int [300001]' [-Warray-bounds]
151 | if(act.size()==0)ans[id]=-1;
| ~~~~~~^
new_home.cpp:63:5: note: while referencing 'ans'
63 | int ans[300001];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2156 ms |
67396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2092 ms |
68064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
