Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
1820 | 18级赵嘉熠 | 【S】T2 区间 | C++ | 运行超时 | 0 | 1000 MS | 73568 KB | 1601 | 2020-11-16 10:13:13 |
#include<bits/stdc++.h> const int N=1000010; #define ll long long using namespace std; ll a[N]; ll n,x; struct node{ ll l,r,maxn,minn; }tree[N<<2]; inline ll read(){ ll s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-'0'; ch=getchar(); } return s*w; } ll askmax(ll i,ll l,ll r) { if(tree[i].l>=l&&tree[i].r<=r) return tree[i].maxn; if(tree[i].r<l||tree[i].l>r) return 0; ll s=0; if(tree[i<<1].r>=l) s=max(askmax(i<<1,l,r),s); if(tree[i<<1|1].l<=r) s=max(askmax(i<<1|1,l,r),s); return s; } ll askmin(ll i,ll l,ll r) { if(tree[i].l>=l&&tree[i].r<=r) return tree[i].minn; if(tree[i].r<l||tree[i].l>r) return 0; ll s=0x3f3f3f3f; if(tree[i*2].r>=l) s=min(askmin(i<<1,l,r),s); if(tree[i*2+1].l<=r) s=min(askmin(i<<1|1,l,r),s); return s; } void build(ll i,ll l,ll r) { tree[i].l=l; tree[i].r=r; if(l==r){ tree[i].maxn=a[l]; tree[i].minn=a[l]; return; } ll mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn); tree[i].maxn=max(tree[i<<1].maxn,tree[i<<1|1].maxn); return; } ll ans; int main(){ n=read(),x=read(); for(ll i=1;i<=n;i++) a[i]=read(); build(1,1,n); for(int l=1;l<=n;l++){ for(int r=l;r<=n;r++){ if(askmax(1,l,r)+askmin(1,l,r)==x) ans++; } } cout<<ans; return 0; }