Submission #1307888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307888		coderelite	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	51 ms	12436 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;
int n;
int a[N],lc[N],rc[N];

void make_tree(void){
	stack<int>st;
	for(int i=0;i<n;i++){
		while(!st.empty()){
			int x=st.top();
			if(a[x]>a[i])break;
			lc[i]=x;
			st.pop();
		}
		if(!st.empty())rc[st.top()]=i;
		st.push(i);
	}
	return;
}

long long dfs(int k){
	long long lcand=0,rcand=0;
	if(lc[k]>=0)lcand=dfs(lc[k])+(k-lc[k]); //abs(k-lc[k])=k-lc[k]
	if(rc[k]>=0)rcand=dfs(rc[k])+(rc[k]-k); //abs(k-rc[k])=rc[k]-k
	return max(lcand,rcand);
}

int main(void){
	int rt=-1;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		lc[i]=-1, rc[i]=-1;
		if(a[i]==n)rt=i;
	}
	make_tree();
	cout << dfs(rt) << endl;
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26