Submission #770550

#	Time	Username	Problem	Language	Result	Execution time	Memory
770550		amirhoseinfar1385	LIS (INOI20_lis)	C++17	100 / 100	2525 ms	215248 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int par[maxn],link[maxn],n,dpnah[maxn],inf=1e7,res=0,nt[maxn];
pair<int,int>all[maxn],dov[maxn];

struct lev{
	vector<int>ind;
	vector<int>x;
	int sz=0,kaf;
	struct segmentmaxa{
		int kaf;
		vector<int>seg;
		void ins(int i,int w){
			if(i==0){
				return ;
			}
			seg[i]=max(seg[i],w);
			return ins((i>>1),w);
		}
		void erase(int i){
			if(i==0){
				return ;
			}
			if(i>=kaf){
				seg[i]=0;
			}
			else{
				seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
			}
			return erase((i>>1));
		}
		int pors(int i,int l,int r,int tl,int tr,int w){
			if(l>r||l>tr||r<tl||tl>tr)
			{
				return -1;
			}
			if(seg[i]<=w){
				return -1;
			}
			if(l==r){
				return l;
			}
			int m=(l+r)>>1;
			int ret=pors((i<<1),l,m,tl,tr,w);
			if(ret!=-1){
				return ret;
			}
			return pors((i<<1)^1,m+1,r,tl,tr,w);
		}
	}maxa;	

	struct segmentmina{
		int kaf;
		vector<int>seg;
		void ins(int i,int w){
			if(i==0){
				return ;
			}
			seg[i]=min(seg[i],w);
			return ins((i>>1),w);
		}
		void erase(int i){
			if(i==0){
				return ;
			}
			if(i>=kaf){
				seg[i]=inf;
			}
			else{
				seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
			}
			return erase((i>>1));
		}
		int pors(int i,int l,int r,int tl,int tr){
			if(l>r||l>tr||r<tl||tl>tr)
			{
				return inf;
			}
			if(l>=tl&&r<=tr){
				return seg[i];
			}
			int m=(l+r)>>1;
			return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
		}
	}mina;	

	void cre(){
		sz=(int)ind.size();
		kaf=nt[sz];
		maxa.seg.resize(kaf*2);
		mina.seg.resize(kaf*2,inf);
		maxa.kaf=kaf;
		mina.kaf=kaf;
	}
	int find(int r){
		int p=upper_bound(ind.begin(),ind.end(),r)-ind.begin();
		p--;
		if(p<0){
			return inf;
		}
		return mina.pors(1,0,kaf-1,0,p);
	}
}lev[maxn];

void updlev(int u,int lv){
	res=max(res,lv);
	int p=lower_bound(lev[lv].ind.begin(),lev[lv].ind.end(),u)-lev[lv].ind.begin();
	lev[lv].maxa.ins(lev[lv].kaf+p,lev[lv].x[p]);
	lev[lv].mina.ins(lev[lv].kaf+p,lev[lv].x[p]);
	while(true){
		int z=lev[lv].maxa.pors(1,0,lev[lv].kaf-1,p+1,lev[lv].sz,lev[lv].x[p]);
		if(z==-1){
			break;
		}
		lev[lv].maxa.erase(lev[lv].kaf+z);
		lev[lv].mina.erase(lev[lv].kaf+z);
		updlev(lev[lv].ind[z],lv+1);
	}
}

void aval(){
	for(int i=0;i<maxn;i++){
		par[i]=i;
	}
	nt[1]=2;
	for(int i=2;i<maxn;i++){
		nt[i]=nt[i/2]*2;
	}
}

int root(int c){
	if(c==par[c]){
		return c;
	}
	return par[c]=root(par[c]);
}

void merge(int u,int v){
	int rootu=root(u),rootv=root(v);
	if(rootu!=rootv){
		par[rootu]=rootv;
	}
}
int kafa=(1<<20);

struct fc{
	int seg[(1<<21)],lazy[(1<<21)];
	fc(){
		for(int i=0;i<(1<<21);i++){
			seg[i]=inf;
		}
	}
	void upd(int i,int w){
		if(i==0){
			return ;
		}
		seg[i]=min(seg[i],w);
		return upd((i>>1),w);
	}
	void calc(int i){
		if(i>=kafa){
			seg[i]+=lazy[i];
			lazy[i]=0;
			return ;
		}
		seg[i]=min(seg[(i<<1)]+lazy[(i<<1)],seg[(i<<1)^1]+lazy[(i<<1)^1]);
	}

	void shift(int i){
		if(lazy[i]==0){
			return ;
		}
		if(i>=kafa){
			return calc(i);
		}
		lazy[(i<<1)]+=lazy[i];
		lazy[(i<<1)^1]+=lazy[i];
		lazy[i]=0;
		calc(i);
	}

	void updsuma(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		shift(i);
		if(l>=tl&&r<=tr){
			lazy[i]+=w;
			return ;
		}
		int m=(l+r)>>1;
		updsuma((i<<1),l,m,tl,tr,w);
		updsuma((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
		return ;
	}

	int porsm(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return inf;
		}
		shift(i);
		if(l>=tl&&r<=tr){
		//	cout<<l<<" "<<r<<" "<<seg[i]<<'\n';
			return seg[i];
		}
		int m=(l+r)>>1;
		return min(porsm((i<<1),l,m,tl,tr),porsm((i<<1)^1,m+1,r,tl,tr));
	}
	int porsw(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return -1;
		}
		shift(i);
		if(seg[i]>w){
			return -1;
		}
		if(l==r){
			return l;
		}
		int m=(l+r)>>1;
		int ret=porsw((i<<1)^1,m+1,r,tl,tr,w);
		if(ret==-1){
			ret=porsw((i<<1),l,m,tl,tr,w);
		}	
		return ret;
	}

	int pors(){
		int mina=porsm(1,0,kafa-1,0,maxn);
		//cout<<mina<<endl;
		return porsw(1,0,kafa-1,0,maxn,mina);
	}
}fc;

vector<int>allv[maxn];
void createall(){
	for(int i=1;i<=n;i++){
		fc.upd(kafa+i,all[i].first);
	}
	for(int i=1;i<=n;i++)
	{
		int w=fc.pors();
		//cout<<i<<" "<<w<<"\n";
		fc.updsuma(1,0,kafa-1,w,w,inf);
		dov[i]=make_pair(all[w].second,w);
		link[w]=i;
		fc.updsuma(1,0,kafa-1,0,w,1);
	}
}

void createlis(){
	vector<int>fake;
	for(int i=1;i<=n;i++){
		int p=lower_bound(fake.begin(),fake.end(),dov[i].first)-fake.begin();
		if(p==(int)fake.size()){
			fake.push_back(dov[i].first);
		}
		else{
			fake[p]=dov[i].first;
		}
		dpnah[i]=p+1;
		for(int j=1;j<=p+1;j++){
			lev[j].ind.push_back(i);
			lev[j].x.push_back(dov[i].first);
		}
	}
}

int wtf(int u){
	for(int i=dov[u].first;i>=1;i--){
		if(lev[i].find(u)<dov[u].first){
			return i;
		}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>all[i].first>>all[i].second;
	}
	createall();
	createlis();
	for(int i=0;i<maxn;i++){
		lev[i].cre();
	}
	for(int i=1;i<=n;i++){
		int ln=wtf(link[i])+1;
	//	cout<<i<<" "<<ln<<" "<<link[i]<<endl;
		updlev(link[i],ln);
		cout<<res<<"\n";
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80