Submission #173251

#	Time	Username	Problem	Language	Result	Execution time	Memory
173251		kig9981	New Home (APIO18_new_home)	C++17	5 / 100	5056 ms	512468 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;

struct Seg
{
	int l, r, v;
	Seg() : l(0), r(0), v(0) {}
} tree[40000000];

const int SZ=1<<19;
multiset<int> P[300000];
tuple<int,int,int> Q[300000], L[300000], R[300000];
int node_cnt, xsz, ans[300000], X[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=node_cnt++;
		add_tree2(n,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=node_cnt++;
		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<=xsz;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;
	for(int i=0;i<N;i++) {
		int p, t, a, b;
		cin>>p>>t>>a>>b; --t;
		X[i]=p;
		L[i]={a,t,p};
		R[i]={b,t,p};
	}
	sort(X,X+N);
	xsz=unique(X,X+N)-X;
	for(int i=0;i<N;i++) get<2>(L[i])=get<2>(R[i])=lower_bound(X,X+xsz,get<2>(L[i]))-X;
	sort(L,L+N);
	sort(R,R+N);
	for(int i=0;i<M;i++) {
		auto &[t,p,idx]=Q[i];
		cin>>p>>t; idx=i;
	}
	sort(Q,Q+M);
	node_cnt=xsz+1;
	for(int c=0;c<M;c++) {
		auto[t,p,i]=Q[c];
		int s=0, e=1e8;
		while(p1<N && 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<N && 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(get_cnt(0,0,xsz-1,xsz-1)<K) {
			ans[i]=-1;
			continue;
		}
		while(s<=e) {
			int m=(s+e)>>1, l, r;
			l=lower_bound(X,X+xsz,p-m)-X;
			r=upper_bound(X,X+xsz,p+m)-X-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 (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:98:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=L[p1++];
              ^
new_home.cpp:113:14: warning: unused variable 't' [-Wunused-variable]
    auto[t,v,p]=R[p2++];
              ^

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