C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 4184K, 提交时间: 2020-08-14 22:47:09

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define per(i,a,n) for(register int i=n;i>=a;--i)
#define mst(x) memset(x,0,sizeof(x));
#define yx_queue priority_queue
#define PI acos(-1)
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef double db;
typedef long long ll;
const ll mod=( 0 ?998244353:1000000007);
const int N=2;
const int inf=1<<30;
const ll llf=9e18;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int f[200100];
int find(int x){ return x==f[x] ? x : f[x] = find(f[x]); }
struct node{
    int x,y,time;
    ll no,w,h;
    friend bool operator<(const node &a,const node&b)
    {
        return a.x>b.x||(a.x==b.x&&a.y<b.y);//sort时<小的在前 优先队列时>小的在前 
    }
};
bool cmp(int x,int  y)
{
    return x>y;
}
int min(int a,int b){if(a>b)return b;else return a;}
int max(int a,int b){if(a<b)return b;else return a;}
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
template<class T>inline void MAX(T &x,T y){if(y>x)x=y;}
template<class T>inline void MIN(T &x,T y){if(y<x)x=y;}
template<class T>inline void rd(T &x){
    x=0;char o,f=1;
    while(o=getchar(),o<48)if(o==45)f=-f;
    do x=(x<<3)+(x<<1)+(o^48);
    while(o=getchar(),o>47);
    x*=f;
}
//while(rp++)

VI g[100010];
int b[100010];
signed main()
{
    ios::sync_with_stdio(false);
    //freopen("c.out","w",stdout);
    int _=1;
    //cin>>_;
    while(_--)
    {
    	int n;
    	cin>>n;
    	int cnt=0;
    	rep(i,1,n)
    	{
    		int a;
    		cin>>a;
    		if(a<cnt)
    		{
    			return cout<<i-1,0;
			}
			per(j,1,a)
			{
				if(b[j])break;
				b[j]=a;
			}
			while(!g[b[a]].empty()&&g[b[a]].back()<a)
			{
				cnt=g[b[a]].back();
				g[b[a]].pop_back();
			}
			g[b[a]].pb(a);
		}
		cout<<n;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 17ms, 内存消耗: 3576K, 提交时间: 2020-08-12 14:17:54

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
int p[N],lim;vector<int>st[N];
int main(){
	int n;scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if(x<lim){printf("%d",i-1);return 0;}
		for(int j=x;j&&!p[j];j--)p[j]=x;
		while(!st[p[x]].empty()&&st[p[x]].back()<x)lim=st[p[x]].back(),st[p[x]].pop_back();
		st[p[x]].push_back(x);
	}
	printf("%d\n",n);
	return 0;
}