C++14(g++5.4) 解法, 执行用时: 202ms, 内存消耗: 16212K, 提交时间: 2019-02-19 16:02:54

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define LL long long
#define mod 1000000007
int a[1000005], b[1000005], L[1000005], L2[1000005], L3[1000005];
int Check(int l, int r, int bas)
{
	int i, sum;
	sum = L3[l-1] = 0;
	for(i=l;i<=r;i++)
	{
		L3[i] = max(L3[i-1], b[i]);
		if(L3[i]-bas==i-l)
			sum++;
	}
	return sum;
}
int Jud(int l, int r)
{
	int i, n, last, ans;
	n = r-l+1;
	for(i=1;i<=n;i++)
		b[i] = a[l+i-1]-l+1;
	last = 1, ans = 1;
	for(i=1;i<=n;i++)
	{
		L2[i] = min(L2[i-1], b[i]);
		if(i==1)
			L2[i] = b[i];
		if(n-L2[i]+1==i)
		{
			if(last==1 && i==n)
				continue;
			if(last==1 || i==n)
				ans = max(ans, 2);
			else
				ans = max(ans, Check(last, i, n-i+1)+2);
			last = i+1;
		}
	}
	return ans;
}
int main(void)
{
	int n, k, i, ans, last, sum;
	scanf("%d%d", &n, &k);
	ans = sum = 0;
	for(i=1;i<=n;i++)
	{
		scanf("%d", &a[i]);
		L[i] = max(L[i-1], a[i]);
		if(L[i]==i)
			sum++;
	}
	last = 1;
	for(i=1;i<=n;i++)
	{
		if(L[i]==i)
		{
			ans = max(ans, Jud(last, i)+sum-1);
			last = i+1;
		}
	}
	if(ans>=k)
		printf("Yes\n");
	else
		printf("Poor Simon\n");
	return 0;
}
/*
10 6
10 9 8 7 4 5 6 3 2 1
5 2
4 1 5 2 3
6 3
1 5 6 2 3 4
*/

C++11(clang++ 3.9) 解法, 执行用时: 168ms, 内存消耗: 12256K, 提交时间: 2019-07-26 22:24:20

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 1000005
int n,m;
int a[N],l[N],r[N],ans;
int t[N];
int q[N];
int check(int l,int r,int st){
	int i,s=0;
	q[l-1]=0;
	for(i=l;i<=r;i++){
		q[i]=max(q[i-1],t[i]);
		if(q[i]==st+i-l)s++;
	}
	return s;
}
int split(int le,int ri){
	int i,n=ri-le+1;
	for(i=1;i<=n;i++)t[i]=a[le+i-1]-le+1;
	l[1]=t[1];
	int ans=1,last=1;
	for(i=1;i<=n;i++){
		if(i!=1)l[i]=min(l[i-1],t[i]);
		if(n+1-l[i]==i){
			if(last==1&&i==n)continue;
			if(last==1||i==n)ans=max(ans,2);
			else ans=max(ans,2+check(last,i,n-i+1));
			last=i+1;
		}
	}
	return ans;
}
int main(){
	int i,s=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++){
		l[i]=max(l[i-1],a[i]);
		if(l[i]==i)r[s++]=i;
	}
	int last=1;
	for(i=0;i<s;i++){
		ans=max(ans,s+split(last,r[i])-1);
		last=r[i]+1;
	}
	if(ans>=m)printf("Yes\n");
	else printf("Poor Simon\n");
	return 0;
}