#include<bits/stdc++.h>
#define maxn 350000
#define maxl 700000
#define bl 1500
using namespace std;
int n,k,q;
int x[maxn];
int a[maxn];
int b[maxn];
int t[maxn];
int l[maxn];
int y[maxn];
int ap[maxn];
bool fn[maxn];
int ans[maxn];
vector<pair<pair<int,int>,int> > v;
vector<pair<int,int> > c;
vector<int> cs;
bool cur[maxn];
int segp[4*maxl];
int segm[4*maxl];
int lc[4*maxl];
int rc[4*maxl];
int ord[bl];
multiset<int> ns[bl];
int cnt=1;
void clear_seg() {
cnt=1;
segp[0]=-1e8;
segm[0]=0;
lc[0]=rc[0]=0;
}
inline void create_children(int id,int l,int r) {
if(lc[id]==0) {
segp[cnt]=-1e8;
segm[cnt]=0;
lc[cnt]=rc[cnt]=0;
lc[id]=cnt++;
}
if(rc[id]==0) {
segp[cnt]=-1e8;
segm[cnt]=0;
lc[cnt]=rc[cnt]=0;
rc[id]=cnt++;
}
}
void update(int id,int l,int r,int p,int q,int a,int b) {
int m=(l+r)/2;
create_children(id,l,r);
if(p<=l && r<=q) {
if(b==1) segp[id]=max(segp[id],a+l-1);
else segm[id]=max(segm[id],a+1-l);
}
if(q<l || r<p) {
return;
}
update(lc[id],l,m,p,q,a,b);
update(rc[id],m+1,r,p,q,a,b);
}
int dif(int id,int l,int r,int x) {
if(id==0 && !(l==1 && r==1e8)) return 0;
int cur=max(segp[id]+x-l,segm[id]+l-x);
int m=(l+r)/2;
if(x<=m) return max(cur,dif(lc[id],l,m,x));
else return max(cur,dif(rc[id],m+1,r,x));
}
int main() {
scanf("%d %d %d",&n,&k,&q);
for(int i=1;i<=n;i++) {
scanf("%d %d %d %d",&x[i],&t[i],&a[i],&b[i]);
v.push_back({{a[i],0},i});
v.push_back({{b[i],2},i});
}
for(int i=1;i<=q;i++) {
scanf("%d %d",&l[i],&y[i]);
v.push_back({{y[i],1},n+i});
}
sort(v.begin(),v.end());
/*for(int i=0;i<v.size();i++) {
cout<<v[i].first.first<<" "<<v[i].first.second<<" "<<v[i].second<<endl;
}*/
for(int i=0;i<v.size();i+=bl) {
int cnt=0;
for(int j=i;j<v.size() && j<i+bl;j++) {
int ind=v[j].second;
if(ind<=n) {
if(ap[t[ind]]==0) {
cur[t[ind]]=true;
ord[t[ind]]=cnt;
cs.push_back(cnt);
cnt++;
}
ap[t[ind]]++;
}
}
for(int j=i-1;j>=0;j--) {
int ind=v[j].second;
if(ind<=n) {
if(v[j].first.second==2) fn[ind]=true;
else {
if(!fn[ind] && ap[t[ind]]==0) {
c.push_back({t[ind],x[ind]});
}
}
}
}
for(int j=i-1;j>=0;j--) {
int ind=v[j].second;
if(ind<=n) {
if(v[j].first.second==2) fn[ind]=true;
else {
if(!fn[ind] && ap[t[ind]]==0) {
if(ap[t[ind]]==0) cnt++;
ap[t[ind]]++;
}
}
}
}
if(cnt==k) {
sort(c.begin(),c.end());
clear_seg();
for(int i=0;i<c.size();i++) {
if(i==0 || c[i-1].first!=c[i].first) {
update(0,1,1e8,1,c[i].second,c[i].second-1,-1);
}
else {
update(0,1,1e8,c[i-1].second,c[i].second,c[i].second-1,-1);
}
if(i+1==c.size() || c[i+1].first!=c[i].first) {
update(0,1,1e8,c[i].second,1e8,1-c[i].second,1);
}
else {
update(0,1,1e8,c[i].second,c[i+1].second,1-c[i].second,1);
}
}
for(int j=i-1;j>=0;j--) {
int ind=v[j].second;
if(ind<=n) {
if(v[j].first.second==2) fn[ind]=true;
else {
if(!fn[ind] && cur[t[ind]]) {
ns[ord[t[ind]]].insert(x[ind]);
}
}
}
}
for(int j=i;j<v.size() && j<i+bl;j++) {
int ind=v[j].second;
if(ind<=n) {
//cout<<j<<" "<<ind<<" "<<ord[t[ind]]<<" "<<v[j].first.second<<endl;
if(v[j].first.second==2) ns[ord[t[ind]]].erase(ns[ord[t[ind]]].find(x[ind]));
else ns[ord[t[ind]]].insert(x[ind]);
}
else {
ind-=n;
//cout<<j<<" "<<ind<<" "<<ind<<" "<<cs.size()<<endl;
for(auto tip:cs) {
//cout<<"\t"<<tip<<" "<<ns[tip].size()<<endl;
if(ns[tip].size()==0) ans[ind]=-1;
}
if(ans[ind]!=-1) {
if(cnt==cs.size()) ans[ind]=0;
else ans[ind]=dif(0,1,1e8,l[ind]);
for(auto tip:cs) {
set<int>::iterator it=ns[tip].lower_bound(l[ind]);
if(it!=ns[tip].end()) ans[ind]=max(ans[ind],(*it)-l[ind]);
if(it!=ns[tip].begin()) {
it--;
ans[ind]=max(ans[ind],l[ind]-(*it));
}
}
}
}
}
}
else {
for(int j=i;j<v.size() && j<i+bl;j++) {
int ind=v[j].second;
if(ind>n) {
ans[ind-n]=-1;
}
}
}
c.clear();
for(int j=0;j<v.size() && j<i+bl;j++) {
int ind=v[j].second;
if(ind<=n) {
cur[t[ind]]=false;
ns[ord[t[ind]]].clear();
ord[t[ind]]=0;
ap[t[ind]]=0;
}
}
cs.clear();
}
for(int j=1;j<=q;j++) printf("%d\n",ans[j]);
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i=0;i<v.size();i+=bl) {
| ~^~~~~~~~~
new_home.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int j=i;j<v.size() && j<i+bl;j++) {
| ~^~~~~~~~~
new_home.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i=0;i<c.size();i++) {
| ~^~~~~~~~~
new_home.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | if(i+1==c.size() || c[i+1].first!=c[i].first) {
| ~~~^~~~~~~~~~
new_home.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int j=i;j<v.size() && j<i+bl;j++) {
| ~^~~~~~~~~
new_home.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | if(cnt==cs.size()) ans[ind]=0;
| ~~~^~~~~~~~~~~
new_home.cpp:180:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int j=i;j<v.size() && j<i+bl;j++) {
| ~^~~~~~~~~
new_home.cpp:188:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | for(int j=0;j<v.size() && j<i+bl;j++) {
| ~^~~~~~~~~
new_home.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d %d %d",&n,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d %d %d %d",&x[i],&t[i],&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d %d",&l[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1639 ms |
789692 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
751 ms |
778496 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
