Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
1832 18级李灏冬 【S】T2 区间 C++ 运行超时 0 1000 MS 27964 KB 1471 2020-11-16 11:21:12

Tests(0/10):


#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; }


测评信息: