Submission #1172915

#TimeUsernameProblemLanguageResultExecution timeMemory
1172915Mauricio_CruzStone Arranging 2 (JOI23_ho_t1)C++20
100 / 100
283 ms34208 KiB
#include <bits/stdc++.h>
using namespace std;

#define srtl(x)sort((x).begin(),(x).end())
#define srtg(x)sort((x).begin(),(x).end(),greater<>())
#define rev(x) reverse((x).begin(),(x).end())
#define lb(x,y) lower_bound(x.begin(),x.end(),y)-x.begin()
#define ub(x,y) upper_bound(x.begin(),x.end(),y)-x.begin()

#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define wa cout<<"wa";
#define tl while(1){}

#define f first
#define s second
#define pb push_back
#define ins insert
#define next next_permutation
#define _b __builtin_popcount

#define pii pair<int,int>
#define piii pair<int,pii>
#define ve vector
#define vi vector<int>
#define vii vector<pii>
#define viii evector<piii>
#define vvi vector<vi>
#define vs vector<string>
#define all(x) x.begin(), x.end()

#define fl fflush(stdout)
#define prtV(x)for(auto i:x)cout<<i<<" ";

#define cint const int
#define int long long

int mod=1000000007;
cint mod1=100000007;
cint mod2=998244353;

int ax[8]={0,1,0,-1,-1,1,1,-1};
int ay[8]={1,0,-1,0,1,-1,1,-1};

//int n,m;

//bool on(int x,int y){return (x>=0&&x<n&&y>=0&&y<m);}
//int euc(int a,int b,int c,int d){return abs(a-c)+abs(b-d);}
#define ve vector
int bp(int x,int y){
	if(y==0)return 1;
	int r=bp(x,y/2);
	return (y&1)?r*r%mod*x%mod:r*r%mod;
}

cint oo=INT_MAX;
const long long OO=LONG_LONG_MAX;



int32_t main(){
	ios;
	
	int n;
	cin>>n;
	stack<pair<int,int>>v;//color, l,r  (r-l)
	map<int,int>m;
	int a[n];
	map<int,int>b;
	int u=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(!m[a[i]]){
			m[a[i]]=++u;
		}
		b[m[a[i]]]=a[i];
		a[i]=m[a[i]];
	}
	bool c[n+1]={};
	
	for(int i=0;i<n;i++){
		int x=a[i];
		if(!c[x]){
			v.push({x,1});
		}
		else{
			int sum=1;
			while(1){
				pii p=v.top();
				v.pop();
				sum+=p.s;
				if(p.f==x){
					v.push({x,sum});
					break;
				}
				else{
					c[p.f]=0;
				}
			}
		}
		c[x]=1;
	}
	vi res;
	while(!v.empty()){
		pii p=v.top();v.pop();
		for(int i=0;i<p.s;i++)res.pb(b[p.f]);
	}
	rev(res);
	//cerr<<"\n\n\n";
	for(int i:res)cout<<i<<"\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...