Submission #7643102

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF LLONG_MAX/5
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
int x[200000];
vector<int> v;
signed main(){
	int a,b;
	cin>>a>>b;
	int cnt=1,z=0,vz,ans=0,an=0;
	bool bo=false,boo=false;
	v.push_back(0);
	f(i,a){
		cin>>x[i];
		if(z<x[i]){
			vz=i;
			z=max(z,x[i]);
			if(boo){
				v.push_back(i-1);
				boo=false;
				bo=false;
			}
		}
		else{
			if(!bo){
				v.push_back(vz);
				bo=true;
			}
			boo=true;
		}
	}
	v.push_back(a);
	for(int i=3;i+1<v.size();i+=2){
		ans+=max((int)0,min({b-(v[i+1]-v[i]+1),v[i+2]-v[i+1],v[i]-v[i-1]}));
	}
	f(i,a){
		if(i){
			if(x[i]>x[i-1])cnt++;
			else{
				an+=max((int)0,cnt-b+1);
				cnt=1;
			}
		}
	}
	an+=max((int)0,cnt-b+1);
	cout<<a-b+1-ans-max((int)0,an-1)<<endl;
}

Submission Info

Judge Result