Submission #211765

#	Time	Username	Problem	Language	Result	Execution time	Memory
211765		zscoder	Sweeping (JOI20_sweeping)	C++17	21 / 100	5777 ms	619132 KiB

sweeping

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

set<int> st[4324242];

void update(int id, int l, int r, int pos, int v)
{
	if(pos>=r||pos<l) return ;
	st[id].insert(v);
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
}

const int INF = int(1e9)+11;
int query(int id, int l, int r, int ql, int qr, int y)
{
	if(ql>=r||l>=qr) return INF;
	if(ql<=l&&r<=qr) 
	{
		auto it = st[id].lower_bound(y);
		if(it==st[id].end()) return INF;
		return (*it);
	}
	int mid=(l+r)>>1;
	return min(query(id*2,l,mid,ql,qr,y),query(id*2+1,mid,r,ql,qr,y));
}

struct node
{
	int lazy;
	int mn;
};

node stx[2222222];
node sty[2222222];
vector<ii> pt;

void combine(int id)
{
	stx[id].mn=min(stx[id*2].mn,stx[id*2+1].mn);
	sty[id].mn=min(sty[id*2].mn,sty[id*2+1].mn);
}

void build(int id, int l, int r)
{
	stx[id].lazy=sty[id].lazy=-1; 
	if(r-l<2)
	{
		stx[id].mn=pt[l].fi;
		sty[id].mn=pt[l].se;
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid); build(id*2+1,mid,r);
	combine(id);
}

void pushx(int id, int l, int r)
{
	if(stx[id].lazy!=-1)
	{
		stx[id].mn=stx[id].lazy;
		if(r-l>=2)
		{
			stx[id*2].lazy=stx[id*2+1].lazy=stx[id].lazy;
		}
		stx[id].lazy=-1;
	}
}

void pushy(int id, int l, int r)
{
	if(sty[id].lazy!=-1)
	{
		sty[id].mn=sty[id].lazy;
		if(r-l>=2)
		{
			sty[id*2].lazy=sty[id*2+1].lazy=sty[id].lazy;
		}
		sty[id].lazy=-1;
	}
}

void updatex(int id, int l, int r, int ql, int qr, int v)
{
	pushx(id,l,r); pushy(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		stx[id].lazy=v;
		pushx(id,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	updatex(id*2,l,mid,ql,qr,v); updatex(id*2+1,mid,r,ql,qr,v);
	combine(id);
}

void updatey(int id, int l, int r, int ql, int qr, int v)
{
	pushy(id,l,r); pushx(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		sty[id].lazy=v;
		pushy(id,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	updatey(id*2,l,mid,ql,qr,v); updatey(id*2+1,mid,r,ql,qr,v);
	combine(id);
}

ii query(int id, int l, int r, int pos)
{
	pushx(id,l,r); pushy(id,l,r);
	if(pos>=r||pos<l) return {-1,-1};
	if(r-l<2)
	{
		return {stx[id].mn,sty[id].mn};
	}
	int mid=(l+r)>>1;
	return max(query(id*2,l,mid,pos),query(id*2+1,mid,r,pos));
}

int getrightmostx(int id, int l, int r, int v) //rightmost x that is <= v
{
	pushx(id,l,r); pushy(id,l,r);
	if(stx[id].mn>v) return -1;
	if(r-l<2) return l;
	int mid=(l+r)>>1;
	if(stx[id*2+1].mn<=v) return getrightmostx(id*2+1,mid,r,v);
	else return getrightmostx(id*2,l,mid,v);
}

int getleftmosty(int id, int l, int r, int v) //leftmost x that is <= v
{
	pushx(id,l,r); pushy(id,l,r);
	if(sty[id].mn>v) return INF;
	if(r-l<2) return l;
	int mid=(l+r)>>1;
	if(sty[id*2].mn<=v) return getleftmosty(id*2,l,mid,v);
	else return getleftmosty(id*2+1,mid,r,v);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m,q; cin>>n>>m>>q;
	vi T;
	for(int i=0;i<m;i++)
	{
		int x,y; cin>>x>>y;
		pt.pb({x,y}); T.pb(0);
	}
	int sub3=1;
	for(int i=1;i<m;i++)
	{
		if(pt[i].fi<pt[i-1].fi||pt[i].se>pt[i-1].se) {sub3=0; break;}
	}
	if(sub3)
	{
		build(1,0,m);
		for(int z=0;z<q;z++)
		{
			int t; cin>>t;
			if(t==1)
			{
				int id; cin>>id; id--;
				ii tmp = query(1,0,m,id);
				cout<<tmp.fi<<' '<<tmp.se<<'\n';
			}
			else if(t==2)
			{
				int l; cin>>l;
				int R = getrightmostx(1,0,m,n-l);
				int L = getleftmosty(1,0,m,l);
				if(L<=R)
				{
					updatex(1,0,m,L,R+1,n-l);
				}
			}
			else
			{
				int l; cin>>l;
				int R = getrightmostx(1,0,m,l);
				int L = getleftmosty(1,0,m,n-l);
				if(L<=R)
				{
					updatey(1,0,m,L,R+1,n-l);
				}
			}
		}
		return 0;
	}
	if(m<=2000&&q<=5000)
	{
		for(int z=0;z<q;z++)
		{
			int t; cin>>t;
			if(t==4)
			{
				int x,y; cin>>x>>y;
				pt.pb({x,y});
			}
			else if(t==3)
			{
				int L; cin>>L;
				for(int i=0;i<pt.size();i++)
				{
					if(L>=pt[i].fi) pt[i].se=max(pt[i].se,n-L);
				}
			}
			else if(t==2)
			{
				int L; cin>>L;
				for(int i=0;i<pt.size();i++)
				{
					if(L>=pt[i].se) pt[i].fi=max(pt[i].fi,n-L);
				}
			}
			else
			{
				int id; cin>>id; id--;
				cout<<pt[id].fi<<' '<<pt[id].se<<'\n';
			}
		}
	}
	else
	{
		vector<pair<ii,int> > queries;
		for(int z=0;z<q;z++)
		{
			int t; cin>>t;
			if(t==4)
			{
				int x,y; cin>>x>>y;
				pt.pb({x,y});
				T.pb(z);
			}
			else if(t==2)
			{
				int L; cin>>L;
				update(1,0,q,z,L);
			}
			else
			{
				int id; cin>>id; id--;
				int y = pt[id].se;
				int ans = query(1,0,q,T[id],q,y);
				int x = pt[id].fi;
				if(ans<INF) x = max(x, n-ans);
				cout<<x<<' '<<y<<'\n';
			}
		}
	}
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:227:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<pt.size();i++)
                 ~^~~~~~~~~~
sweeping.cpp:235:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<pt.size();i++)
                 ~^~~~~~~~~~

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