結果
問題 | No.1394 Changing Problems |
ユーザー | beet |
提出日時 | 2021-02-12 23:20:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,513 bytes |
コンパイル時間 | 2,315 ms |
コンパイル使用メモリ | 215,684 KB |
実行使用メモリ | 22,536 KB |
最終ジャッジ日時 | 2024-07-20 01:00:50 |
合計ジャッジ時間 | 22,738 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 758 ms
22,408 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
ソースコード
#include <bits/stdc++.h>using namespace std;using Int = long long;const char newl = '\n';template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}template<typename T=Int>vector<T> read(size_t n){vector<T> ts(n);for(size_t i=0;i<n;i++) cin>>ts[i];return ts;}template <typename T,typename E>struct SegmentTree{using F = function<T(T,T)>;using G = function<T(T,E)>;using H = function<E(E,E)>;Int n,height;F f;G g;H h;T ti;E ei;vector<T> dat;vector<E> laz;SegmentTree(F f,G g,H h,T ti,E ei):f(f),g(g),h(h),ti(ti),ei(ei){}void init(Int n_){n=1;height=0;while(n<n_) n<<=1,height++;dat.assign(2*n,ti);laz.assign(2*n,ei);}void build(const vector<T> &v){Int n_=v.size();init(n_);for(Int i=0;i<n_;i++) dat[n+i]=v[i];for(Int i=n-1;i;i--)dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);}inline T reflect(Int k){return laz[k]==ei?dat[k]:g(dat[k],laz[k]);}inline void propagate(Int k){if(laz[k]==ei) return;laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);dat[k]=reflect(k);laz[k]=ei;}inline void thrust(Int k){for(Int i=height;i;i--) propagate(k>>i);}inline void recalc(Int k){while(k>>=1)dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));}void update(Int a,Int b,E x){if(a>=b) return;thrust(a+=n);thrust(b+=n-1);for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1) laz[l]=h(laz[l],x),l++;if(r&1) --r,laz[r]=h(laz[r],x);}recalc(a);recalc(b);}void set_val(Int a,T x){thrust(a+=n);dat[a]=x;laz[a]=ei;recalc(a);}T query(Int a,Int b){if(a>=b) return ti;thrust(a+=n);thrust(b+=n-1);T vl=ti,vr=ti;for(Int l=a,r=b+1;l<r;l>>=1,r>>=1) {if(l&1) vl=f(vl,reflect(l++));if(r&1) vr=f(reflect(--r),vr);}return f(vl,vr);}template<typename C>Int find(Int st,C &check,T &acc,Int k,Int l,Int r){if(l+1==r){acc=f(acc,reflect(k));return check(acc)?k-n:-1;}propagate(k);Int m=(l+r)>>1;if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);if(st<=l and !check(f(acc,dat[k]))){acc=f(acc,dat[k]);return -1;}Int vl=find(st,check,acc,(k<<1)|0,l,m);if(~vl) return vl;return find(st,check,acc,(k<<1)|1,m,r);}template<typename C>Int find(Int st,C &check){T acc=ti;return find(st,check,acc,1,0,n);}};//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);Int n;cin>>n;auto as=read(n);if(n==1){Int q;cin>>q;for(Int i=0;i<q;i++){Int p,x;cin>>p>>x;cout<<x+1<<newl;}return 0;}const Int INF = 1e9;auto f=[&](Int a,Int b){return max(a,b);};auto g=[&](Int a,Int b){return a+b;};SegmentTree<Int, Int> seg(f,g,g,-INF,0);seg.build(vector<Int>(n-1,0));for(Int i=0;i<n-1;i++)seg.update(i,n-1,-1);auto floor=[&](Int a,Int b){if(0<=a) return a/b;if(abs(a)%b==0) return a/b;return -(abs(a)/b+1);};auto mod=[&](Int a,Int b){return (a%b+b)%b;};auto idx=[&](Int a){return n-2-mod(n-2-a,n-1);};Int num=0;for(Int a:as){seg.update(idx(a),n-1,+1);num+=floor(n-2-a,n-1);}multiset<Int> ms(as.begin(),as.end());Int q;cin>>q;for(Int i=0;i<q;i++){Int p,x;cin>>p>>x;p--;Int &a=as[p];seg.update(idx(a),n-1,-1);num-=floor(n-2-a,n-1);ms.erase(ms.find(a));a=x;seg.update(idx(a),n-1,+1);num+=floor(n-2-a,n-1);ms.emplace(a);if(*--ms.end()<=n-2){assert(num>=0);cout<<0<<newl;continue;}Int pre=seg.query(0,n-1);assert(1<=pre);Int t=max<decltype(num)>(0,-(num+pre));assert(num+t+pre>=0);if(t>0) assert(num+(t-1)+pre<0);// while(t>0 and num+(t-1)+pre>=0) t--;auto check=[&](Int v){return num+t+v>=0;};Int s=seg.find(0,check);assert(0<=s and s<n-1);Int ans=(n-1)*t+s;chmax(ans,*--ms.end()-(n-2));// cout<<*--ms.end()<<' '<<ans<<endl;if(false){Int cnt=0;for(Int a:as){assert(a-ans<=n-2);cnt+=floor(n-2-a+ans,n-1);}assert(cnt>=ans);}cout<<ans<<newl;cout<<flush;}return 0;}