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;
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;
}
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,y;
cin>>x>>y;
v.push_back({x,i,y,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
{
int minn=1e9;
for(auto it=s[j].begin();it!=s[j].end();it++)
{
minn=min(minn,abs(h.x-*it));
}
maxx=max(maxx,minn);
/*auto it=s[j].begin();
if(h.x<*it)maxx=max(maxx,*it-h.x);
else
{
it=s[j].end();it--;
if(*it<=h.x)maxx=max(maxx,h.x-*it);
else
{
it=s[j].upper_bound(h.x);
maxx=max(maxx,h.x-*it);
it++;
maxx=max(maxx,*it-h.x);
}
}*/
}
}
ans[h.t]=maxx;
}
}
for(int i=1;i<=q;i++)
cout<<ans[i]<<endl;
}
int main()
{
read();
solve();
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/
Compilation message (stderr)
new_home.cpp: In function 'void solve()':
new_home.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<hour>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
# | 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... |