#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+8;
const ll INF=1e18;
const int siz=1010101;
struct seg
{
int t[2020202];
seg()
{
fill(t,t+2020202,-inf);
}
void si(int n,int s,int e,int x,int p)
{
if(s==e)
{
t[n]=p==inf?-p:p;
return;
}
int m=s+e>>1;
if(x>m)
si(n*2+1,m+1,e,x,p);
else
si(n*2,s,m,x,p);
t[n]=max(t[n*2],t[n*2+1]);
return;
}
int sq(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return -inf;
if(S<=s&&e<=E)
return t[n];
int m=s+e>>1;
return max(sq(n*2,s,m,S,E),sq(n*2+1,m+1,e,S,E));
}
}st1,st2;
priority_queue<int>pq1[siz],pq2[siz];
priority_queue<int>dl1[siz],dl2[siz];
inline int get(priority_queue<int>&x,priority_queue<int>&y)
{
while(!y.empty()&&x.top()==y.top())
x.pop(),y.pop();
return x.empty()?-inf:x.top();
}
vector<int>cp;
inline void add1(int x0,int x)
{
int ci=upper_bound(all(cp),x)-cp.begin()-1;
pq1[ci].ep(-x0);
st1.si(1,0,cp.size()-1,ci,get(pq1[ci],dl1[ci]));
return;
}
inline void add2(int x0,int x)
{
int ci=lower_bound(all(cp),x)-cp.begin();
pq2[ci].ep(x0);
st2.si(1,0,cp.size()-1,ci,get(pq2[ci],dl2[ci]));
return;
}
inline void del1(int x0,int x)
{
int ci=upper_bound(all(cp),x)-cp.begin()-1;
dl1[ci].ep(-x0);
st1.si(1,0,cp.size()-1,ci,get(pq1[ci],dl1[ci]));
return;
}
inline void del2(int x0,int x)
{
int ci=lower_bound(all(cp),x)-cp.begin();
dl2[ci].ep(x0);
st2.si(1,0,cp.size()-1,ci,get(pq2[ci],dl2[ci]));
return;
}
multiset<int>pts[siz];
inline void add(int tp,int x)
{
auto it=pts[tp].lower_bound(x);
int nxt=*it;
if(nxt==x)
{
pts[tp].ep(x);
return;
}
int prv=*--it;
del1(prv,prv+nxt>>1);
del2(nxt,prv+nxt>>1);
add1(prv,prv+x>>1);
add2(x,prv+x>>1);
add1(x,x+nxt>>1);
add2(nxt,x+nxt>>1);
pts[tp].ep(x);
return;
}
inline void del(int tp,int x)
{
pts[tp].erase(pts[tp].find(x));
auto it=pts[tp].lower_bound(x);
int nxt=*it;
if(nxt==x)
return;
int prv=*--it;
del1(prv,prv+x>>1);
del2(x,prv+x>>1);
del1(x,x+nxt>>1);
del2(nxt,x+nxt>>1);
add1(prv,prv+nxt>>1);
add2(nxt,prv+nxt>>1);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,k,q;
cin>>n>>k>>q;
vector<pair<int,pi> >va,vb;
for(int i=0;i<n;i++)
{
int x,t,a,b;
cin>>x>>t>>a>>b;
va.eb(a-1,pi(x*2,t-1));
vb.eb(b,pi(x*2,t-1));
}
vector<pair<int,pi> >qv;
for(int i=0;i<q;i++)
{
int x,y;
cin>>x>>y;
qv.eb(y,pi(x*2,i));
cp.eb(x*2);
}
cp.eb(-inf);
cp.eb(inf);
sort(all(cp));
cp.erase(unique(all(cp)),cp.end());
for(int i=0;i<k;i++)
{
add1(-inf,0);
add2(inf,0);
pts[i].ep(-inf);
pts[i].ep(inf);
}
sort(all(va));
sort(all(vb));
sort(all(qv));
vector<int>ans(q,0);
int c=0;
int ai=0;
int bi=0;
vector<int>ct(k,0);
for(auto&t:qv)
{
while(ai<va.size()&&va[ai].fi<t.fi)
{
add(va[ai].se.se,va[ai].se.fi);
if(ct[va[ai].se.se]++==0)
c++;
ai++;
}
while(bi<vb.size()&&vb[bi].fi<t.fi)
{
del(vb[bi].se.se,vb[bi].se.fi);
if(--ct[vb[bi].se.se]==0)
c--;
bi++;
}
if(c<k)
{
ans[t.se.se]=-1;
continue;
}
int x=lower_bound(all(cp),t.se.fi)-cp.begin();
int m1=st1.sq(1,0,cp.size()-1,x,cp.size()-1);
int m2=st2.sq(1,0,cp.size()-1,0,x);
ans[t.se.se]=max(t.se.fi+m1,m2-t.se.fi);
}
for(int i=0;i<q;i++)
cout<<ans[i]/2<<'\n';
cout.flush();
return 0;
}
Compilation message
new_home.cpp: In member function 'void seg::si(int, int, int, int, int)':
new_home.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
new_home.cpp: In member function 'int seg::sq(int, int, int, int, int)':
new_home.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
new_home.cpp: In function 'void add(int, int)':
new_home.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
del1(prv,prv+nxt>>1);
~~~^~~~
new_home.cpp:101:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
del2(nxt,prv+nxt>>1);
~~~^~~~
new_home.cpp:102:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add1(prv,prv+x>>1);
~~~^~
new_home.cpp:103:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add2(x,prv+x>>1);
~~~^~
new_home.cpp:104:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add1(x,x+nxt>>1);
~^~~~
new_home.cpp:105:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add2(nxt,x+nxt>>1);
~^~~~
new_home.cpp: In function 'void del(int, int)':
new_home.cpp:117:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
del1(prv,prv+x>>1);
~~~^~
new_home.cpp:118:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
del2(x,prv+x>>1);
~~~^~
new_home.cpp:119:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
del1(x,x+nxt>>1);
~^~~~
new_home.cpp:120:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
del2(nxt,x+nxt>>1);
~^~~~
new_home.cpp:121:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add1(prv,prv+nxt>>1);
~~~^~~~
new_home.cpp:122:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add2(nxt,prv+nxt>>1);
~~~^~~~
new_home.cpp: In function 'int main()':
new_home.cpp:168:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ai<va.size()&&va[ai].fi<t.fi)
~~^~~~~~~~~~
new_home.cpp:175:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(bi<vb.size()&&vb[bi].fi<t.fi)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
190116 KB |
Output is correct |
| 2 |
Incorrect |
135 ms |
190072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
190116 KB |
Output is correct |
| 2 |
Incorrect |
135 ms |
190072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1607 ms |
237868 KB |
Output is correct |
| 2 |
Correct |
1225 ms |
229552 KB |
Output is correct |
| 3 |
Correct |
1325 ms |
269108 KB |
Output is correct |
| 4 |
Correct |
1563 ms |
254876 KB |
Output is correct |
| 5 |
Correct |
1117 ms |
242644 KB |
Output is correct |
| 6 |
Correct |
1241 ms |
242132 KB |
Output is correct |
| 7 |
Correct |
1317 ms |
269100 KB |
Output is correct |
| 8 |
Correct |
1556 ms |
254944 KB |
Output is correct |
| 9 |
Correct |
1608 ms |
248688 KB |
Output is correct |
| 10 |
Correct |
1391 ms |
243028 KB |
Output is correct |
| 11 |
Correct |
1125 ms |
241964 KB |
Output is correct |
| 12 |
Correct |
1271 ms |
243076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3603 ms |
239372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
190116 KB |
Output is correct |
| 2 |
Incorrect |
135 ms |
190072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
190116 KB |
Output is correct |
| 2 |
Incorrect |
135 ms |
190072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
