#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct Seg
{
int l, r, v;
Seg() : l(0), r(0), v(0) {}
};
const int SZ=1<<19;
vector<Seg> tree;
vector<int> X;
multiset<int> P[300000];
vector<tuple<int,int,int,int>> S;
vector<tuple<int,int,int>> Q, L, R;
int ans[300000];
void add_tree2(int n, int v, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(s==e) {
tree[p].v+=v;
return;
}
if(n<=m) {
if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(Seg());
add_tree2(n,v,tree[p].l,s,m);
}
else {
if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
add_tree2(n,v,tree[p].r,m+1,e);
}
tree[p].v=tree[tree[p].l].v+tree[tree[p].r].v;
}
void add_tree(int x, int y, int v)
{
for(++x;x<=X.size();x+=x&-x) add_tree2(y,v,x);
}
int get_cnt2(int n1, int n2, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(p==0 || n2<n1 || n2<s || e<n1) return 0;
if(n1<=s && e<=n2) return tree[p].v;
return get_cnt2(n1,n2,tree[p].l,s,m)+get_cnt2(n1,n2,tree[p].r,m+1,e);
}
int get_cnt(int n1, int n2, int p)
{
int ret=0;
for(++p;p;p-=p&-p) ret+=get_cnt2(n1,n2,p);
return ret;
}
int get_cnt(int x1, int y1, int x2, int y2)
{
return get_cnt(y1,y2,x2)-get_cnt(y1,y2,x1-1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, K, M, p1=0, p2=0;
cin>>N>>K>>M;
S.resize(N);
for(auto &[p,t,a,b]: S) {
cin>>p>>t>>a>>b; --t;
X.push_back(p);
}
sort(X.begin(),X.end());
X.resize(unique(X.begin(),X.end())-X.begin());
Q.resize(M);
for(int i=0;i<M;i++) {
auto &[t,p,idx]=Q[i];
cin>>p>>t; idx=i;
}
sort(Q.begin(),Q.end());
for(auto &[p,t,a,b]: S) {
p=lower_bound(X.begin(),X.end(),p)-X.begin();
L.emplace_back(a,t,p);
R.emplace_back(b,t,p);
}
sort(L.begin(),L.end());
sort(R.begin(),R.end());
tree.resize(X.size()+1);
for(auto[t,p,i]: Q) {
int s=0, e=1e8;
while(p1<L.size() && get<0>(L[p1])<=t) {
auto[t,v,p]=L[p1++];
auto r=P[v].lower_bound(p), l=r;
if(r!=P[v].end() && *r==p) {
P[v].insert(p);
continue;
}
if(r!=P[v].begin()) l=r,--l;
else l=P[v].end();
if(l!=P[v].end() && r!=P[v].end()) add_tree(*l,*r,1);
if(l!=P[v].end()) add_tree(*l,p,-1);
if(r!=P[v].end()) add_tree(p,*r,-1);
add_tree(p,p,1);
P[v].insert(p);
}
while(p2<R.size() && get<0>(R[p2])<t) {
auto[t,v,p]=R[p2++];
P[v].erase(P[v].find(p));
auto r=P[v].lower_bound(p), l=r;
if(r!=P[v].end() && *r==p) continue;
if(r!=P[v].begin()) l=r,--l;
else l=P[v].end();
if(l!=P[v].end() && r!=P[v].end()) add_tree(*l,*r,-1);
if(l!=P[v].end()) add_tree(*l,p,1);
if(r!=P[v].end()) add_tree(p,*r,1);
add_tree(p,p,-1);
}
if(tree[1].v<K) {
ans[i]=-1;
continue;
}
while(s<=e) {
int m=(s+e)>>1, l, r;
l=lower_bound(X.begin(),X.end(),p-m)-X.begin();
r=upper_bound(X.begin(),X.end(),p+m)-X.begin()-1;
if(l<=r && get_cnt(l,l,r,r)==K) e=m-1;
else s=m+1;
}
if(s>1e8) ans[i]=-1;
else ans[i]=s;
}
for(int i=0;i<M;i++) cout<<ans[i]<<'\n';
return 0;
}
Compilation message
new_home.cpp: In function 'void add_tree(int, int, int)':
new_home.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(++x;x<=X.size();x+=x&-x) add_tree2(y,v,x);
~^~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:102:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p1<L.size() && get<0>(L[p1])<=t) {
~~^~~~~~~~~
new_home.cpp:103:14: warning: unused variable 't' [-Wunused-variable]
auto[t,v,p]=L[p1++];
^
new_home.cpp:117:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p2<R.size() && get<0>(R[p2])<t) {
~~^~~~~~~~~
new_home.cpp:118:14: warning: unused variable 't' [-Wunused-variable]
auto[t,v,p]=R[p2++];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14456 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14508 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14456 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14508 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4702 ms |
488848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5041 ms |
489676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14456 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14508 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14456 KB |
Output is correct |
| 3 |
Correct |
15 ms |
14508 KB |
Output is correct |
| 4 |
Incorrect |
15 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
