ST表WA了倒数第二个点,求助
查看原帖
ST表WA了倒数第二个点,求助
287227
deicide·楼主2023/1/19 17:26
#include<iostream>
#include<cmath>
using namespace std;
int a[10000001][12];
int b[10000001][12];
int n,m,c;
int v[12];
int main()
{
  cin>>n>>m>>c;
  v[0]=1;
  for(int i=1;i<=12&&v[i-1]<=m;i++)
  	  v[i]=v[i-1]*2;
  for(int i=1;i<=n;i++)
  {
  	cin>>a[i][0];
  	b[i][0]=a[i][0];
  }
  for(int j=1;v[j]<=m;j++)
  	for(int i=1;i+v[j]-1<=n;i++)
  	{
  		a[i][j]=min(a[i][j-1],a[i+v[j-1]][j-1]);
  		b[i][j]=max(b[i][j-1],b[i+v[j-1]][j-1]);
  	}
  	int l=0;
  	int s=log2(m);
  for(int i=1;i<=n-m+1;i++)
  {
	  if(max(b[i][s],b[i+m-v[s]][s])-min(a[i][s],a[i+m-v[s]][s])<=c)
	  {
	     cout<<i<<endl;
	     l=1;
	 }
   }
   if(l==0)cout<<"NONE";
   return 0;
}
2023/1/19 17:26
加载中...