Submission #444653

#	Time	Username	Problem	Language	Result	Execution time	Memory
444653		kig9981	Sweeping (JOI20_sweeping)	C++17	100 / 100	4097 ms	122912 KiB

sweeping

#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 Splay
{
	int p, l, r, c, x, y, yl;
	Splay() : p(0), l(0), r(0), c(1), x(0), y(0), yl(-1) {}
} tree[1500001];

const int SZ=1<<21;
vector<pair<int,int>> Q;
vector<int> x;
int mtree[2*SZ], lz[2*SZ], R[1500000];

void lazy(int c)
{
	if(tree[c].l) tree[tree[c].l].x=tree[c].x;
	if(tree[c].r) tree[tree[c].r].x=tree[c].x;
	tree[c].y=max(tree[c].y,tree[c].yl);
	if(tree[c].l) tree[tree[c].l].yl=max(tree[tree[c].l].yl,tree[c].yl);
	if(tree[c].r) tree[tree[c].r].yl=max(tree[tree[c].r].yl,tree[c].yl);
	tree[c].yl=-1;
}

void update(int c) {tree[c].c=tree[tree[c].l].c+tree[tree[c].r].c+1;}

void rotate(int c)
{
	int p=tree[c].p;
	if(tree[p].l==c) {
		if(tree[c].r) tree[tree[c].r].p=p;
		tree[p].l=tree[c].r;
		tree[c].r=p;
	}
	else {
		if(tree[c].l) tree[tree[c].l].p=p;
		tree[p].r=tree[c].l;
		tree[c].l=p;
	}
	if(tree[p].p) (tree[tree[p].p].l==p ? tree[tree[p].p].l:tree[tree[p].p].r)=c;
	tree[c].p=tree[p].p;
	tree[p].p=c;
	update(p); update(c);
}

void splay(int c)
{
	while(tree[c].p) {
		int p=tree[c].p;
		if(tree[p].p) lazy(tree[p].p);
		lazy(p); lazy(c);
		if(tree[p].p) rotate((tree[tree[p].p].l==p)==(tree[p].l==c) ? p:c);
		rotate(c);
	}
	lazy(c);
}

int add_node(int c, int v)
{
	splay(c);
	for(;;) {
		lazy(c);
		if(tree[c].y<tree[v].y) {
			if(tree[c].r==0) {
				splay(c);
				if(tree[v].r=tree[c].r) tree[tree[v].r].p=v;
				tree[c].r=v;
				tree[v].p=c;
				update(v); update(c);
				return c;
			}
			c=tree[c].r;
		}
		else {
			if(tree[c].l==0) {
				splay(c);
				if(tree[v].l=tree[c].l) tree[tree[v].l].p=v;
				tree[c].l=v;
				tree[v].p=c;
				update(v); update(c);
				return c;
			}
			c=tree[c].l;
		}
	}
}

void lazy_propagation(int bit, int s, int e)
{
	mtree[bit]=max(mtree[bit],lz[bit]);
	if(s<e) {
		if(mtree[2*bit]<0x7f7f7f7f) lz[2*bit]=max(lz[2*bit],lz[bit]);
		if(mtree[2*bit+1]<0x7f7f7f7f) lz[2*bit+1]=max(lz[2*bit+1],lz[bit]);
	}
	else if(R[s]>-1) {
		tree[R[s]].yl=max(tree[R[s]].yl,lz[bit]);
		lazy(R[s]);
	}
	lz[bit]=-1;
}

void push(int n)
{
	int bit=1, s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		lazy_propagation(bit,s,e);
		if(n<=m) tie(bit,e)=make_pair(2*bit,m);
		else tie(bit,s)=make_pair(2*bit+1,m+1);
	}
	lazy_propagation(bit,s,e);
}

void dfs(int &c, int p)
{
	int l=tree[p].l, r=tree[p].r;
	lazy(p); tree[p].p=tree[p].l=tree[p].r=0;
	if(l) dfs(c,l);
	c=add_node(c,p);
	if(r) dfs(c,r);
}

void query(int n1, int n2, int p, int v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1 || mtree[bit]>v) return;
	if(s==e) {
		int &c=R[m];
		for(;;) {
			lazy(c);
			if(tree[c].y>v) {
				if(tree[c].l==0) {
					splay(c);
					break;
				}
				c=tree[c].l;
			}
			else {
				if(tree[c].r==0) {
					splay(c);
					if(tree[c].r) {
						for(lazy(c=tree[c].r);tree[c].l;) lazy(c=tree[c].l);
						splay(c);
					}
					break;
				}
				c=tree[c].r;
			}
		}
		mtree[SZ+p]=min(mtree[SZ+p],mtree[bit]);
		if(tree[c].y<=v) {
			mtree[bit]=0x7f7f7f7f;
			if(R[p]==-1) {
				swap(c,R[p]);
				tree[R[p]].x=x[p];
				lazy(R[p]);
				return;
			}
			if(tree[c].c>tree[R[p]].c) swap(c,R[p]);
			dfs(R[p],c); c=-1; tree[R[p]].x=x[p]; lazy(R[p]);
		}
		else {
			mtree[bit]=tree[c].y;
			tree[v=tree[c].l].p=0;
			tree[c].l=0; update(c);
			if(R[p]==-1) {
				R[p]=v;
				tree[R[p]].x=x[p]; lazy(R[p]);
				return;
			}
			if(tree[v].c>tree[R[p]].c) swap(v,R[p]);
			dfs(R[p],v); tree[R[p]].x=x[p]; lazy(R[p]);
		}
		return;
	}
	query(n1,n2,p,v,2*bit,s,m);
	query(n1,n2,p,v,2*bit+1,m+1,e);
	mtree[bit]=min(mtree[2*bit],mtree[2*bit+1]);
}

void set_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		lz[bit]=v;
		lazy_propagation(bit,s,e);
		return;
	}
	set_tree(n1,n2,v,2*bit,s,m);
	set_tree(n1,n2,v,2*bit+1,m+1,e);
	mtree[bit]=min(mtree[2*bit],mtree[2*bit+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 L, N, B, M;
	cin>>L>>N>>M; tree[0].c=0;
	memset(lz,-1,sizeof(lz));
	memset(R,-1,sizeof(R));
	memset(mtree,0x7f,sizeof(mtree));
	for(int i=1;i<=N;i++) {
		int a, b;
		cin>>a>>b;
		x.push_back(a);
		tree[i].x=a;
		tree[i].y=b;
	}
	Q.resize(M); B=N;
	for(auto &[t,a]: Q) {
		cin>>t>>a;
		if(t==2) x.push_back(L-a);
		else if(t==4) {
			int b;
			cin>>b;
			x.push_back(a);
			tree[++N].x=a;
			tree[a=N].y=b;
		}
	}
	sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
	for(int i=1;i<=B;i++) {
		int p=lower_bound(x.begin(),x.end(),tree[i].x)-x.begin();
		if(R[p]==-1) R[p]=i;
		else R[p]=add_node(R[p],i);
		mtree[SZ+p]=min(mtree[SZ+p],tree[i].y);
	}
	for(int i=SZ;--i;) mtree[i]=min(mtree[2*i],mtree[2*i+1]);
	for(auto[t,a]: Q) {
		int p;
		if(t==1) {
			splay(a);
			R[p=lower_bound(x.begin(),x.end(),tree[a].x)-x.begin()]=a;
			push(p);
			cout<<tree[a].x<<' '<<tree[a].y<<'\n';
		}
		else if(t==2) {
			p=lower_bound(x.begin(),x.end(),L-a)-x.begin();
			push(p); query(0,p-1,p,a);
			for(p+=SZ;p>>=1;) mtree[p]=min(max(mtree[2*p],lz[2*p]),max(mtree[2*p+1],lz[2*p+1]));
		}
		else if(t==3) {
			p=upper_bound(x.begin(),x.end(),a)-x.begin()-1;
			set_tree(0,p,L-a);
		}
		else {
			p=lower_bound(x.begin(),x.end(),tree[a].x)-x.begin();
			push(p);
			if(R[p]==-1) R[p]=a;
			else R[p]=add_node(R[p],a);
			p+=SZ;
			for(mtree[p]=min(mtree[p],tree[a].y);p>>=1;) mtree[p]=min(max(mtree[2*p],lz[2*p]),max(mtree[2*p+1],lz[2*p+1]));
		}
	}
	return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'int add_node(int, int)':
sweeping.cpp:75:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   75 |     if(tree[v].r=tree[c].r) tree[tree[v].r].p=v;
      |        ~~~~~~~~~^~~~~~~~~~
sweeping.cpp:86:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   86 |     if(tree[v].l=tree[c].l) tree[tree[v].l].p=v;
      |        ~~~~~~~~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25