View Code of Problem 3605

#include<cstdio>
#include<cassert>
#include<set>
#include<map>
#include<cmath>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
typedef long double db;
void gn(int &x){
	char c;while((c=getchar())<'0'||c>'9');x=c-'0';
	while((c=getchar())>='0'&& c<='9')x=x*10+c-'0';
}
int n;
int a[111111],ord[111111];
int cut[111111],con[111111];
set<int> cuts;
#define inf 1000000000
inline void cutit(int x){
	if(!cut[x]){
		cut[x]=1;
		cuts.insert(x);
	}
}

int seg[444444];
int l1,r1,I,v;
void build(int l,int r,int x){
	if(l==r){
		seg[x]=a[l];
	}else{
		int mid=l+r>>1;
		build(l,mid,x<<1);
		build(mid+1,r,x<<1|1);
		seg[x]=max(seg[x<<1],seg[x<<1|1]);
	}
}
void upd(int l,int r,int x){
	if(l==r)seg[x]=-inf;
	else{
		int mid=l+r>>1;
		if(I<=mid)upd(l,mid,x<<1);
		else upd(mid+1,r,x<<1|1);
		seg[x]=max(seg[x<<1],seg[x<<1|1]);
	}
}
void que(int l,int r,int x){
	if(l1<=l && r<=r1)v=max(v,seg[x]);
	else{
		int mid=l+r>>1;
		if(l1<=mid)que(l,mid,x<<1);
		if(r1>mid)que(mid+1,r,x<<1|1);
	}
}
void conit(int x){
	if(!con[x]){
		con[x]=1;
		I=x;
		upd(1,n,1);
	}
}
int ans[111111];
int main()
{
	/*freopen("1.in","r",stdin);
	freopen("ans.out","w",stdout);*/
	int tes;
	scanf("%d",&tes);
	while(tes--){
		cuts.clear();
		scanf("%d",&n);
		/*memset(ord,0,sizeof(ord));*/
		for (int i=1;i<=n;i++)gn(a[i]),ord[a[i]]=i,cut[i]=con[i]=0;
		/*for (int i=1;i<=n;i++)assert(ord[i]);*/
		cut[n+1]=con[n+1]=0;
		cutit(1);
		cutit(n+1);
		build(1,n,1);
		for (int k=1;k<=n;k++){
			int i=ord[k];
			int rma=-inf;
			if(!cut[i+1])rma=a[i+1];
			int lma=-inf;
			if(!con[i+1]){
				set<int>::iterator it=cuts.lower_bound(i+1);it--;
				l1=*it,r1=i,v=-inf;
				que(1,n,1);
				lma=v;
			}
			if(rma>lma){
				ans[k]=rma;
				conit(i+1);
			}else{
				ans[k]=lma;
				int pos=ord[lma];
				cutit(pos);
				cutit(i+1);
				for (int j=pos+1;j<=i;j++)conit(j);
			}
		}
		for (int i=1;i<=n;i++){
			if(i>1)printf(" ");
			printf("%d",ans[i]);
		}
		printf("\n");
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 3605