Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
45373 lgh 数列操作2 C++ 通过 100 612 MS 2692 KB 1629 2022-02-17 13:05:46

Tests(10/10):


#include<cstdio> #include<cmath> #include<algorithm> #include<vector> #define inf 0x7f7f7f7f #define ll long long #define N 100009 using namespace std; ll v[N],tag[N]; vector<ll> a[2600]; int blo[N]; int n,blo_len; inline ll read() { char ch=getchar(); ll f=1,ret=0; while(ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=ret*10+ch-'0'; ch=getchar(); } return ret; } void reinit(int x) { a[x].clear(); for (int i=(x-1)*blo_len+1; i<=min(n,x*blo_len); i++) a[x].push_back(v[i]); sort(a[x].begin(),a[x].end()); } void change(int l,int r,int d) { for (int i=l; i<=min(blo[l]*blo_len,r); i++) v[i]+=d; reinit(blo[l]); if (blo[l]!=blo[r]) { for (int i=(blo[r]-1)*blo_len+1; i<=r; i++) v[i]+=d; reinit(blo[r]); } for (int i=blo[l]+1; i<=blo[r]-1; i++) tag[i]+=d; } ll query(int l,int r,int d) { ll ret=-inf,cur; for (int i=l; i<=min(blo[l]*blo_len,r); i++) { cur=v[i]+tag[blo[l]]; if (cur<d&&cur>ret) ret=cur; } if (blo[l]!=blo[r]) for (int i=(blo[r]-1)*blo_len+1; i<=r; i++) { cur=v[i]+tag[blo[r]]; if (cur<d&&cur>ret) ret=cur; } for (int i=blo[l]+1; i<=blo[r]-1; i++) { int x=d-tag[i],id=lower_bound(a[i].begin(),a[i].end(),x)-a[i].begin()-1; if (a[i][id]<x) ret=max(ret,a[i][id]+tag[i]); } return ret==-inf?-1:ret; } int main() { n=read(); blo_len=sqrt(n); for (int i=1; i<=n; i++) v[i]=read(); for (int i=1; i<=n; i++) blo[i]=(i-1)/blo_len+1,a[blo[i]].push_back(v[i]); for (int i=1; i<=blo[n]; i++) sort(a[i].begin(),a[i].end()); for (int i=1; i<=n; i++) { int opt=read(),l=read(),r=read(); ll d=read(); if (!opt) change(l,r,d); else printf("%lld\n",query(l,r,d)); } return 0; }


测评信息: