Submission #173165

#	Time	Username	Problem	Language	Result	Execution time	Memory
173165		kig9981	New Home (APIO18_new_home)	C++17	5 / 100	5157 ms	861524 KiB

new_home

#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;

vector<int> X, T, tree[300001], TX[300001];
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)
{
	for(++n;n<=X.size();n+=n&-n) tree[p][lower_bound(TX[p].begin(),TX[p].end(),n)-TX[p].begin()]+=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 n, int p)
{
	int ret=0, t;
	if(TX[p].empty()) return 0;
	for(++n;n;n-=n&-n) if(n<=TX[p].back()) {
		t=lower_bound(TX[p].begin(),TX[p].end(),n)-TX[p].begin();
		if(TX[p][t]==n) ret+=tree[p][t];
	}
	return ret;
}

int get_cnt2(int n1, int n2, int p)
{
	return get_cnt2(n2,p)-get_cnt2(n1-1,p);
}

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);
}

void add_value2(int x, int v)
{
	for(++v;v<=X.size();v+=v&-v) TX[x].push_back(v);
}

void add_value(int x, int y)
{
	for(++x;x<=X.size();x+=x&-x) add_value2(x,y);
}

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, p3=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);
		T.push_back(a);
		T.push_back(b);
	}
	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;
		T.push_back(t);
	}
	sort(Q.begin(),Q.end());
	sort(T.begin(),T.end());
	T.resize(unique(T.begin(),T.end())-T.begin());
	for(auto &[p,t,a,b]: S) {
		p=lower_bound(X.begin(),X.end(),p)-X.begin();
		a=lower_bound(T.begin(),T.end(),a)-T.begin();
		b=lower_bound(T.begin(),T.end(),b)-T.begin();
		L.emplace_back(a,t,p);
		R.emplace_back(b,t,p);
	}
	for(auto &[t,p,idx]: Q) t=lower_bound(T.begin(),T.end(),t)-T.begin();
	sort(L.begin(),L.end());
	sort(R.begin(),R.end());
	for(int t=0;t<T.size();t++) {
		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_value(*l,*r);
			if(l!=P[v].end()) add_value(*l,p);
			if(r!=P[v].end()) add_value(p,*r);
			add_value(p,p);
			P[v].insert(p);
		}
		while(p3<R.size() && get<0>(R[p3])==t) {
			auto[t,v,p]=R[p3++];
			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_value(*l,*r);
			if(l!=P[v].end()) add_value(*l,p);
			if(r!=P[v].end()) add_value(p,*r);
			add_value(p,p);
		}
	}
	for(int i=X.size();i;i--) {
		sort(TX[i].begin(),TX[i].end());
		TX[i].resize(unique(TX[i].begin(),TX[i].end())-TX[i].begin());
		tree[i].resize(TX[i].size());
	}
	for(int t=p1=p3=0;t<T.size();t++) {
		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<Q.size() && get<0>(Q[p2])==t) {
			auto[t,p,i]=Q[p2++];
			int s=0, e=1e8;
			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;
		}
		while(p3<R.size() && get<0>(R[p3])==t) {
			auto[t,v,p]=R[p3++];
			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);
		}
	}
	for(int i=0;i<M;i++) cout<<ans[i]<<'\n';
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void add_tree2(int, int, int)':
new_home.cpp:21:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(++n;n<=X.size();n+=n&-n) tree[p][lower_bound(TX[p].begin(),TX[p].end(),n)-TX[p].begin()]+=v;
          ~^~~~~~~~~~
new_home.cpp: In function 'void add_tree(int, int, int)':
new_home.cpp:26: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 'void add_value2(int, int)':
new_home.cpp:59:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(++v;v<=X.size();v+=v&-v) TX[x].push_back(v);
          ~^~~~~~~~~~
new_home.cpp: In function 'void add_value(int, int)':
new_home.cpp:64:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(++x;x<=X.size();x+=x&-x) add_value2(x,y);
          ~^~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:101:20: warning: unused variable 'p' [-Wunused-variable]
  for(auto &[t,p,idx]: Q) t=lower_bound(T.begin(),T.end(),t)-T.begin();
                    ^
new_home.cpp:101:20: warning: unused variable 'idx' [-Wunused-variable]
new_home.cpp:104:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t=0;t<T.size();t++) {
              ~^~~~~~~~~
new_home.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<L.size() && get<0>(L[p1])==t) {
         ~~^~~~~~~~~
new_home.cpp:106:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=L[p1++];
              ^
new_home.cpp:120:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p3<R.size() && get<0>(R[p3])==t) {
         ~~^~~~~~~~~
new_home.cpp:121:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=R[p3++];
              ^
new_home.cpp:138:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t=p1=p3=0;t<T.size();t++) {
                    ~^~~~~~~~~
new_home.cpp:139:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<L.size() && get<0>(L[p1])==t) {
         ~~^~~~~~~~~
new_home.cpp:140:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=L[p1++];
              ^
new_home.cpp:154:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2<Q.size() && get<0>(Q[p2])==t) {
         ~~^~~~~~~~~
new_home.cpp:155:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,p,i]=Q[p2++];
              ^
new_home.cpp:167:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p3<R.size() && get<0>(R[p3])==t) {
         ~~^~~~~~~~~
new_home.cpp:168:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=R[p3++];
              ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20