제출 #1153836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153836		i271828	Po (COCI21_po)	C++20	20 / 70	23 ms	1864 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int MAX=100005;

int N=6;
int A[MAX]={1,2,3,2,1,3};

int P[MAX];
int L[MAX];
int R[MAX];

bool done=false;
vector<int> roots;
vector<int> new_roots;

void resolve(int i, int x){
	if (A[i]==x){
		if (L[i]!=-1) resolve(L[i],x);
		if (R[i]!=-1) resolve(R[i],x);
	}else{
		new_roots.push_back(i);
	}
}

int main(){
	//*
	cin>>N;
	for (int i=0;i<N;i++) cin>>A[i];/**/
	
	for (int i=0;i<N;i++){
		L[i]=-1,R[i]=-1,P[i]=-1;
	}
	int root=0;
	for (int i=1;i<N;i++){
		int x=i-1;
		
		while (x!=-1&&A[x]>=A[i]) x=P[x];
		if (x==-1) L[i]=root, P[root]=i, root=i;
		else{
			P[i]=x;
			if (R[x]==-1) R[x]=i;
			else L[i]=R[x], P[R[x]]=i, R[x]=i;
		}
	}
	
	roots.push_back(root);
	int ans=0;
	while (roots.size()){
		new_roots.clear();
		for (auto r: roots){
			ans++;
			resolve(r, A[r]);
		}
		roots.clear();
		for (auto r: new_roots){
			roots.push_back(r);
		}
	}
	cout<<ans;
}

• Subtask 1: 20 / 70