记录编号	303677	评测结果	WWWWWWWWWW
题目名称	[NOIP 2013]花匠	最终得分	0
用户昵称	‎MistyEye	是否通过	未通过
代码语言	C++	运行时间	0.162 s
提交时间	2016-09-06 11:07:12	内存使用	2.99 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long ll;
ll read(){
	ll x=0,f=1; char ch;
	while(ch=getchar(),!isdigit(ch)) if(ch=='-') f=-1;
	x = ch-'0';
	while(ch=getchar(), isdigit(ch)) x = x*10+ch-'0';
	return x*f;
}
const ll maxn = 100005;
int N, h[maxn];
struct Node{
	int h, l;
	Node(int h=0, int l=0):h(h), l(l){}
};
Node s1[maxn], s2[maxn];
int cur1, cur2;
int ans1[maxn], ans2[maxn];

int main(){
	freopen("FlowerNOIP2013.in","r",stdin); freopen("FlowerNOIP2013.out","w",stdout);
	N = read();
	int ans = 1;
	for(int i=1; i<=N; ++i) h[i] = read();
	s1[++cur1] = s2[++cur2] = Node(h[1], 1);
	for(int i=2; i<=N; ++i){
		int k1 = 0, k2 = 0, l1 = 0, l2 = 0;
		while(cur1 && s1[cur1].h >= h[i]) k1 = max(k1, s1[cur1].l), --cur1;
		while(cur2 && s2[cur2].h <= h[i]) k2 = max(k2, s2[cur2].l), --cur2;
		for(int j=1; j<=cur1; ++j) l1 = max(l1, s1[cur1].l);
		for(int j=1; j<=cur2; ++j) l2 = max(l2, s2[cur2].l);
		s1[++cur1] = Node(h[i], max(k1, l2+1));
		s2[++cur2] = Node(h[i], max(k2, l1+1));
		ans = max(ans, s1[cur1].l);
		ans = max(ans, s2[cur2].l);
		ans1[i] = s1[cur1].l;
		ans2[i] = s2[cur2].l;
		printf("%d %d\n", cur1, cur2);
	}
	printf("%d\n", ans);
	if(ans!=3) {
		for(int i=1; i<=N; ++i) printf("%d ", ans1[i]); puts("");
		for(int i=1; i<=N; ++i) printf("%d ", ans2[i]); puts("");
	}
	getchar(),getchar();
	return 0;
}
/*
1441. [NOIP2013]花匠
 */
/*
5
5 3 2 1 2
 */