一个点TLE求助
查看原帖
一个点TLE求助
843293
D2019ly楼主2022/11/1 19:21

还能怎么优化啊?

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

int n,b;
int a[100005];
int da[100005],xiao[100005];
int cnt=0;


int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>b;
	int loc;
	for(register int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]==b)loc=i;
		if(a[i]>b)da[i]=da[i-1]+1;
		else da[i]=da[i-1];
		if(a[i]<b)xiao[i]=xiao[i-1]+1;
		else xiao[i]=xiao[i-1];
	}
//	for(int i=1;i<=n;i++)cout<<da[i]<<" "<<xiao[i]<<endl;
	for(register int step=1;step<=n;step++)
	{
		if(!(step&1))continue;
		for(register int i=1;i+step-1<=n;i++)
		{
			int j=i+step-1;
			if(j<loc||i>loc)continue;
			if(da[j]+xiao[i-1]==xiao[j]+da[i-1])cnt++;
		}
	}
	cout<<cnt<<endl;		
	
	return 0;
}
2022/11/1 19:21
加载中...