Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
1832 | 18级李灏冬 | 【S】T2 区间 | C++ | 运行超时 | 0 | 1000 MS | 27964 KB | 1471 | 2020-11-16 11:21:12 |
#include<bits/stdc++.h> using namespace std; int n,x; int val[1000005]; int minv[1000005*4]; int maxv[1000005*4]; int ans; void pushup(int id){ minv[id]=min(minv[id<<1],minv[id<<1|1]); maxv[id]=max(maxv[id<<1],maxv[id<<1|1]); } void build(int id,int l,int r){ if(l==r){ minv[id]=val[l]; maxv[id]=val[l]; return ; } int mid=(l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); pushup(id); } int query_min(int id,int l,int r,int x,int y){ if(x<=l && r<=y){ return minv[id]; } int mid=(l+r)>>1; int res=0x3f3f3f3f; if(x<=mid) res=min(res,query_min(id<<1,l,mid,x,y)); if(y>mid) res=min(res,query_min(id<<1|1,mid+1,r,x,y)); return res; } int query_max(int id,int l,int r,int x,int y){ if(x<=l && r<=y){ return maxv[id]; } int mid=(l+r)>>1; int res=-1; if(x<=mid) res=max(res,query_max(id<<1,l,mid,x,y)); if(y>mid) res=max(res,query_max(id<<1|1,mid+1,r,x,y)); return res; } int main(){ cin>>n>>x; memset(minv,0x3f,sizeof(minv)); for(int i=1;i<=n;i++){ scanf("%d",&val[i]); } build(1,1,n); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ int tmp=query_min(1,1,n,i,j)+query_max(1,1,n,i,j); if(tmp==x) ans++; } } cout<<ans<<endl; return 0; }