#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
class Line{
public:
int l,r;
int a,b;
Line() : l(0), r(0), a(0), b(0) {}
Line(int lll, int rr, int aa, int bb) : l(lll), r(rr), a(aa), b(bb) {}
bool operator<(const Line& other)const{
if(l==other.l){
if(r==other.r){
if(a==other.a){
return b<other.b;
}
return a<other.a;
}
return r<other.r;
}
return l<other.l;
}
};
class Point{
public:
int x,t,a,b;
bool helnox;
Point(int xx, int tt, int aa, int bb, bool h) : x(xx), t(tt), a(aa), b(bb), helnox(h) {}
bool operator<(const Point& other)const{
if(a==other.a){
if(b==other.b){
if(x==other.x){
return t<other.t;
}
return x<other.x;
}
return b<other.b;
}
return a<other.a;
}
};
ll ttt;
const ll INF=1e18;
const int MOD=1e9+7;
const ll N=1e6+7;
ll n,m,k;
set<Line>s[N];
vector<Point>d[N];
vector<Point>ps;
int ps_cnt[N];
vector<pair<int,bool>>pss;
vector<Line>ls[N];
vector<pair<Line, bool>>p[N];
vector<int>times;
unordered_map<int,int>compress;
vector<pair<int,int>>t1[4*N],t2[4*N];
vector<int>pf1[4*N],pf2[4*N];
vector<pair<int,int>>qs;
void update1(int v, int tl, int tr, int l, int r, pair<int,int> vl){
if(l>r)return;
if(tl==l&&tr==r){
t1[v].push_back(vl);
}
else{
int tm=(tl+tr)/2;
update1(2*v,tl,tm,l,min(r,tm),vl);
update1(2*v+1,tm+1,tr,max(l,tm+1),r,vl);
}
}
void update2(int v, int tl, int tr, int l, int r, pair<int,int> vl){
if(l>r)return;
if(tl==l&&tr==r){
t2[v].push_back({vl.ss,vl.ff});
}
else{
int tm=(tl+tr)/2;
update2(2*v,tl,tm,l,min(r,tm),vl);
update2(2*v+1,tm+1,tr,max(l,tm+1),r,vl);
}
}
void tpel(int v, int tl, int tr){
// cout<<"["<<times[tl]<<", "<<times[tr]<<"]: ";
// for(pii&x:t1[v]){
// // cout<<"("<<x.ff<<", "<<x.ss<<"), ";
// }
// cout<<endl;
if(t1[v].size()){
pf1[v].push_back(t1[v][0].ss);
for(int i=1;i<t1[v].size();i++){
pf1[v].push_back(max(pf1[v].back(),t1[v][i].ss));
}
}
if(t2[v].size()){
pf2[v].push_back(t2[v][0].ss);
for(int i=1;i<t2[v].size();i++){
pf2[v].push_back(min(pf2[v].back(),t2[v][i].ss));
}
}
if(tl!=tr){
int tm=(tl+tr)/2;
tpel(2*v,tl,tm);
tpel(2*v+1,tm+1,tr);
}
}
int query1(int v, int tl, int tr, int x, int t){
auto it=upper_bound(t1[v].begin(),t1[v].end(),make_pair(x,MOD));
int cur=0;
if(it!=t1[v].begin()){
it--;
int ind=it-t1[v].begin();
cur=pf1[v][ind];
}
if(tl!=tr){
int tm=(tl+tr)/2;
if(tm>=t)cur=max(cur,query1(2*v,tl,tm,x,t));
else cur=max(cur,query1(2*v+1,tm+1,tr,x,t));
}
return cur;
}
int query2(int v, int tl, int tr, int x, int t){
auto it=upper_bound(t2[v].begin(),t2[v].end(),make_pair(x,MOD));
int cur=MOD;
if(it!=t2[v].begin()){
it--;
int ind=it-t2[v].begin();
cur=pf2[v][ind];
}
if(tl!=tr){
int tm=(tl+tr)/2;
if(tm>=t)cur=min(cur,query2(2*v,tl,tm,x,t));
else cur=min(cur,query2(2*v+1,tm+1,tr,x,t));
}
return cur;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("output.txt","w",stdout);
cin>>n>>k>>m;
for(int c=1;c<=k;c++){
s[c].insert(Line(0,1e8+1,0,0));
}
for(int i=0;i<n;i++){
int x,t,a,b;
cin>>x>>t>>a>>b;
d[t].push_back(Point(x,t,a,b,false));
d[t].push_back(Point(x,t,b,b,true));
ps.push_back(Point(x,t,a,b,false));
ps.push_back(Point(x,t,b+1,b,true));
}
sort(ps.begin(),ps.end());
set<int>baner;
for(int i=1;i<=k;i++)baner.insert(i);
for(Point&pp:ps){
if(pp.helnox){
ps_cnt[pp.t]--;
if(ps_cnt[pp.t]==0){
baner.insert(pp.t);
}
}
else{
if(ps_cnt[pp.t]==0){
baner.erase(pp.t);
}
ps_cnt[pp.t]++;
}
pss.push_back({pp.a,baner.size()!=0});
// cout<<pp.a<<" "<<(baner.size()!=0)<<endl;
}
for(int c=1;c<=k;c++){
sort(d[c].begin(),d[c].end());
for(int i=0;i<d[c].size();i++){
if(!d[c][i].helnox){
auto it=s[c].upper_bound(Line(d[c][i].x,MOD,MOD,MOD));
it--;
Line x=*it;
x.b=d[c][i].a-1;
ls[c].push_back(x);
Line fst((*it).l,d[c][i].x,d[c][i].a,0);
Line snd(d[c][i].x,(*it).r,d[c][i].a,0);
s[c].erase(it);
s[c].insert(fst);
s[c].insert(snd);
}
else{
auto it=s[c].lower_bound(Line(d[c][i].x,0,0,0));
auto it2=it;
it2--;
Line fst=*it2;
fst.b=d[c][i].a;
ls[c].push_back(fst);
Line snd=*it;
snd.b=d[c][i].a;
ls[c].push_back(snd);
Line x(fst.l,snd.r,d[c][i].a+1,0);
s[c].erase(it);
s[c].erase(it2);
s[c].insert(x);
}
}
for(int i=0;i<ls[c].size();i++){
if(ls[c][i].l!=0&&ls[c][i].r!=1e8+1){
int mid=(ls[c][i].l+ls[c][i].r)/2;
p[c].push_back({Line(ls[c][i].l,mid,ls[c][i].a,ls[c][i].b),false});
p[c].push_back({Line(mid+1,ls[c][i].r,ls[c][i].a,ls[c][i].b),true});
}
else if(ls[c][i].l==0){
Line x=ls[c][i];
x.l=1;
p[c].push_back({x,true});
}
else{
Line x=ls[c][i];
x.r=1e8;
p[c].push_back({x,false});
}
}
// cout<<c<<":\n";
// cout<<"ls\n";
// for(Line& x:ls[c]){
// cout<<"["<<x.l<<", "<<x.r<<"] -> ("
// <<x.a<<", "<<x.b<<")"<<endl;
// }
// cout<<"p\n";
// for(int i=0;i<p[c].size();i++){
// cout<<"["<<p[c][i].first.l<<", "<<p[c][i].first.r<<"] -> ("
// <<p[c][i].first.a<<", "<<p[c][i].first.b<<"), "<<p[c][i].second<<endl;
// }
for(pair<Line,bool>& x:p[c]){
times.push_back(x.ff.a);
times.push_back(x.ff.b);
}
}
for(int i=0;i<m;i++){
int x,t;
cin>>x>>t;
times.push_back(t);
qs.push_back({x,t});
}
sort(times.begin(),times.end());
auto it=unique(times.begin(),times.end());
times.resize(it-times.begin());
for(int i=0;i<times.size();i++){
compress[times[i]]=i;
}
n=times.size();
for(int c=1;c<=k;c++){
for(pair<Line,bool>&x:p[c]){
if(x.ff.r>=x.ff.l&&x.ff.a!=0&&x.ff.b!=1e8+1&&x.ff.a<=x.ff.b){
if(x.ss){
update1(1,0,n-1,compress[x.ff.a],compress[x.ff.b],{x.ff.l,x.ff.r});
}
else{
update2(1,0,n-1,compress[x.ff.a],compress[x.ff.b],{x.ff.l,x.ff.r});
}
// cout<<"QUERY: "<<1<<" "<<0<<" "<<n-1<<" "<<x.ff.a<<
// " "<<x.ff.b<<" {"<<x.ff.l<<", "<<x.ff.r<<"}\n";
}
}
}
for(int v=1;v<=4*n;v++){
sort(t1[v].begin(),t1[v].end());
sort(t2[v].begin(),t2[v].end());
}
// cout<<"t1:\n";
// tpel1(1,0,n-1);
// cout<<endl<<"t2:\n";
// tpel2(1,0,n-1);
tpel(1,0,n-1);
// for(int v=1;v<=4*n;v++){
// for(auto x:t1[v]){
// cout<<x.ff<<" "<<x.ss<<"\t";
// }
// cout<<endl;
// }
for(int i=0;i<qs.size();i++){
int t=qs[i].ss;
int x=qs[i].ff;
// cout<<t<<endl;
auto it=upper_bound(pss.begin(),pss.end(),make_pair(t,true));
if(it==pss.begin()){
cout<<-1<<endl;
continue;
}
it--;
if((*it).ss){
cout<<-1<<endl;
continue;
}
int r=query1(1,0,n-1,x,compress[t]);
int l=query2(1,0,n-1,x,compress[t]);
cout<<max(x-l,r-x)<<endl;
}
}
Compilation message
new_home.cpp: In function 'void tpel(int, int, int)':
new_home.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i=1;i<t1[v].size();i++){
| ~^~~~~~~~~~~~~
new_home.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=1;i<t2[v].size();i++){
| ~^~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:189:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for(int i=0;i<d[c].size();i++){
| ~^~~~~~~~~~~~
new_home.cpp:218:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | for(int i=0;i<ls[c].size();i++){
| ~^~~~~~~~~~~~~
new_home.cpp:260:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
260 | for(int i=0;i<times.size();i++){
| ~^~~~~~~~~~~~~
new_home.cpp:293:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
293 | for(int i=0;i<qs.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
493468 KB |
Output is correct |
| 2 |
Correct |
202 ms |
493396 KB |
Output is correct |
| 3 |
Correct |
198 ms |
493388 KB |
Output is correct |
| 4 |
Incorrect |
197 ms |
493432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
493468 KB |
Output is correct |
| 2 |
Correct |
202 ms |
493396 KB |
Output is correct |
| 3 |
Correct |
198 ms |
493388 KB |
Output is correct |
| 4 |
Incorrect |
197 ms |
493432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3887 ms |
927216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3810 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
493468 KB |
Output is correct |
| 2 |
Correct |
202 ms |
493396 KB |
Output is correct |
| 3 |
Correct |
198 ms |
493388 KB |
Output is correct |
| 4 |
Incorrect |
197 ms |
493432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
493468 KB |
Output is correct |
| 2 |
Correct |
202 ms |
493396 KB |
Output is correct |
| 3 |
Correct |
198 ms |
493388 KB |
Output is correct |
| 4 |
Incorrect |
197 ms |
493432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
