結果
問題 | No.1394 Changing Problems |
ユーザー | LayCurse |
提出日時 | 2021-02-12 23:02:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 20,632 bytes |
コンパイル時間 | 4,508 ms |
コンパイル使用メモリ | 224,468 KB |
実行使用メモリ | 24,960 KB |
最終ジャッジ日時 | 2024-07-20 00:26:48 |
合計ジャッジ時間 | 25,124 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 650 ms
24,832 KB |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 14 ms
5,376 KB |
testcase_11 | AC | 15 ms
5,376 KB |
testcase_12 | AC | 15 ms
5,376 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 1,000 ms
24,832 KB |
testcase_17 | AC | 994 ms
24,960 KB |
testcase_18 | AC | 1,007 ms
24,960 KB |
testcase_19 | AC | 1,011 ms
24,832 KB |
testcase_20 | AC | 999 ms
24,832 KB |
testcase_21 | AC | 986 ms
24,704 KB |
testcase_22 | AC | 1,000 ms
24,832 KB |
testcase_23 | AC | 1,013 ms
24,832 KB |
testcase_24 | AC | 996 ms
24,832 KB |
testcase_25 | AC | 981 ms
24,832 KB |
testcase_26 | AC | 445 ms
23,296 KB |
testcase_27 | AC | 439 ms
23,296 KB |
testcase_28 | AC | 442 ms
23,424 KB |
testcase_29 | AC | 531 ms
24,320 KB |
testcase_30 | AC | 527 ms
24,448 KB |
testcase_31 | AC | 537 ms
24,704 KB |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;void*wmem;char memarr[314572800];template<class S, class T> inline S min_L(S a,T b){return a<=b?a:b;}template<class S, class T> inline S max_L(S a,T b){return a>=b?a:b;}template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){walloc1d(arr, x2-x1, mem);(*arr) -= x1;}inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline int rd_int(void){int x;rd(x);return x;}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}inline void wt_L(long long x){int s=0;int m=0;char f[20];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}template<class T, class S> T inline fDiv(T a, S b){T m;if(b < 0){a = -a;b = -b;}m = a % b;if(m == 0){return a / b;}if(m < 0){m += b;}return (a - m) / b;}template<class S, class T> inline S moddw_L(S a, const T b){a %= b;if(a < 0){a += b;}return a;}template<class S, class T> inline S chmin(S &a, T b){if(a>b){a=b;}return a;}template<class T> struct segtree{int N;int logN;T*sum;T*mn;int*mnind;T*fixval;char*fixed;T*addval;void malloc(int maxN, int once = 0){int i;for(i=1;i<maxN;i*=2){;}sum = new T[2*i];mn = new T[2*i];mnind = new int[2*i];fixval = new T[i];addval = new T[i];fixed = new char[i];if(once){setN(maxN);}}void walloc(int maxN, int once = 0, void **mem = &wmem){int i;for(i=1;i<maxN;i*=2){;}walloc1d(&sum, 2*i, mem);walloc1d(&mn, 2*i, mem);walloc1d(&mnind, 2*i, mem);walloc1d(&fixval, i, mem);walloc1d(&addval, i, mem);walloc1d(&fixed, i, mem);if(once){setN(maxN);}}void free(void){delete [] sum;delete [] mn;delete [] mnind;delete [] fixval;delete [] addval;delete [] fixed;}T& operator[](int i){return sum[N+i];}void setN(int n, int zerofill = 1, int dobuild = 1){int i;for(i=1,logN=0;i<n;i*=2,logN++){;}N = i;if(zerofill){for(i=(0);i<(N);i++){sum[N+i] = 0;}}if(dobuild){build();}}void build(void){int i;for(i=(0);i<(N);i++){mn[N+i] = sum[N+i];mnind[N+i] = i;}for(i=N-1;i;i--){sum[i] = sum[2*i] + sum[2*i+1];if(mn[2*i] <= mn[2*i+1]){mn[i] = mn[2*i];mnind[i] = mnind[2*i];}else{mn[i] = mn[2*i+1];mnind[i] = mnind[2*i+1];}}int XNa8avth = N;for(i=(1);i<(XNa8avth);i++){fixed[i] = 0;}int sMcf5Tpe = N;for(i=(1);i<(sMcf5Tpe);i++){addval[i] = 0;}}inline void push_one(int a, int sz, int st){if(fixed[a]){if(sz > 1){fixed[a*2] = fixed[a*2+1] = 1;fixval[a*2] = fixval[a*2+1] = fixval[a];sum[a*2] = sum[a*2+1] = sz * fixval[a];mn[a*2] = mn[a*2+1] = fixval[a];mnind[a*2] = st;mnind[a*2+1] = st + sz;}else{sum[a*2] = sum[a*2+1] = sz * fixval[a];mn[a*2] = mn[a*2+1] = fixval[a];mnind[a*2] = st;mnind[a*2+1] = st + sz;}fixed[a] = 0;addval[a] = 0;return;}if(addval[a] != 0){if(sz > 1){if(fixed[a*2]){fixval[a*2] += addval[a];}else{addval[a*2] += addval[a];}if(fixed[a*2+1]){fixval[a*2+1] += addval[a];}else{addval[a*2+1] += addval[a];}sum[a*2] += sz * addval[a];sum[a*2+1] += sz * addval[a];mn[a*2] += addval[a];mn[a*2+1] += addval[a];}else{sum[a*2] += sz * addval[a];sum[a*2+1] += sz * addval[a];mn[a*2] += addval[a];mn[a*2+1] += addval[a];}addval[a] = 0;return;}}inline void push(int a){int i;int aa = a - N;int nd;int sz;int st;for(i=logN;i;i--){nd = a>>i;sz = 1<<(i-1);st = 2 * sz * (aa>>i);push_one(nd, sz, st);}}inline void build(int a){int sz = 1;int st = a - N;while(a > 1){if(a%2){st += sz;}a /= 2;sz *= 2;if(fixed[a]){sum[a] = sz * fixval[a];mn[a] = fixval[a];}else{sum[a] = sum[a*2] + sum[a*2+1];if(mn[a*2] <= mn[a*2+1]){mn[a] = mn[a*2];mnind[a] = mnind[a*2];}else{mn[a] = mn[a*2+1];mnind[a] = mnind[a*2+1];}if(addval[a] != 0){mn[a] += addval[a];sum[a] += sz * addval[a];}}}}inline void change(int a, int b, T val){int sz = 1;int aa;int bb;int st_a = a;int st_b = b;if(a >= b){return;}aa = (a += N);bb = (b += N);push(a);push(b-1);if(a%2){sum[a] = mn[a] = val;a++;st_a += sz;}if(b%2){b--;st_b -= sz;sum[b] = mn[b] = val;}a /= 2;b /= 2;while(a < b){sz *= 2;if(a%2){fixed[a]=1;fixval[a]=val;sum[a] = sz * val;mn[a] = val;mnind[a] = st_a;a++;st_a += sz;}if(b%2){b--;st_b -= sz;fixed[b]=1;fixval[b]=val;sum[b] = sz * val;mn[b] = val;mnind[b] = st_b;}a /= 2;b /= 2;}build(aa);build(bb-1);}inline void add(int a, int b, T val){int sz = 1;int aa;int bb;if(a >= b){return;}aa = (a += N);bb = (b += N);push(a);push(b-1);if(a%2){sum[a] += val;mn[a] += val;a++;}if(b%2){b--;sum[b] += val;mn[b] += val;}a /= 2;b /= 2;while(a < b){sz *= 2;if(a%2){if(fixed[a]){fixval[a] += val;}else{addval[a] += val;}sum[a] += sz * val;mn[a] += val;a++;}if(b%2){b--;if(fixed[b]){fixval[b] += val;}else{addval[b] += val;}sum[b] += sz * val;mn[b] += val;}a /= 2;b /= 2;}build(aa);build(bb-1);}inline pair<T,int> getMin(int a, int b){pair<T,int> res;pair<T,int> tmp;int fga = 0;int fgb = 0;a += N;b += N;push(a);push(b-1);while(a < b){if(a%2){if(fga){res =min_L(res, make_pair(mn[a], mnind[a]));}else{res = make_pair(mn[a], mnind[a]);fga = 1;}a++;}if(b%2){b--;if(fgb){tmp =min_L(make_pair(mn[b], mnind[b]), tmp);}else{tmp = make_pair(mn[b], mnind[b]);fgb = 1;}}a /= 2;b /= 2;}if(fga==1 && fgb==0){return res;}if(fga==0 && fgb==1){return tmp;}if(fga==1 && fgb==1){res =min_L(res, tmp);return res;}return res;}inline T getMinVal(int a, int b){T res;T tmp;int fga = 0;int fgb = 0;a += N;b += N;push(a);push(b-1);while(a < b){if(a%2){if(fga){res =min_L(res, mn[a]);}else{res = mn[a];fga = 1;}a++;}if(b%2){b--;if(fgb){tmp =min_L(mn[b], tmp);}else{tmp = mn[b];fgb = 1;}}a /= 2;b /= 2;}if(fga==1 && fgb==0){return res;}if(fga==0 && fgb==1){return tmp;}if(fga==1 && fgb==1){res =min_L(res, tmp);return res;}return res;}inline int getMinInd(int a, int b){return getMin(a,b).second;}inline T getSum(int a, int b){T res;T tmp;int fga = 0;int fgb = 0;a += N;b += N;push(a);push(b-1);while(a < b){if(a%2){if(fga){res = res + sum[a];}else{res = sum[a];fga = 1;}a++;}if(b%2){b--;if(fgb){tmp = sum[b] + tmp;}else{tmp = sum[b];fgb = 1;}}a /= 2;b /= 2;}if(fga==1 && fgb==0){return res;}if(fga==0 && fgb==1){return tmp;}if(fga==1 && fgb==1){res = res + tmp;return res;}return res;}};template<class SVAL, class SFUN> struct segtree_rh{int N;int logN;int trueN;SVAL*val;SFUN*fun;char*dofun;void malloc(int maxN, int once = 0);void walloc(int maxN, int once = 0, void **mem = &wmem);void free(void);SVAL& operator[](int i);void setN(int n, int zerofill = 1, int dobuild = 1);void build(void);inline void push_one(int a);inline void push(int a);inline void build(int a);inline void change(int a, int b, SFUN f);inline SVAL get(int a, int b);template<bool (*f)(SVAL)> int max_right(int a, int mx);template<bool (*f)(SVAL)> int max_right(int a);template<bool (*f)(SVAL)> int min_left(int b, int mn);template<bool (*f)(SVAL)> int min_left(int b);};long long segtree_rh_apply(long long f, long long a){return a+f;}long long segtree_rh_merge(long long a, long long b){return min_L(a, b);}long long segtree_rh_compose(long long f, long long g){return f+g;}long long val;bool f(long long a){return a >= val;}int N;int A[200000];int Q;int IND;int X;long long ds;segtree<long long> ms;segtree_rh<long long,long long> mms;int main(){int i, jZyWAPpY;wmem = memarr;rd(N);{int KL2GvlyY;for(KL2GvlyY=(0);KL2GvlyY<(N);KL2GvlyY++){rd(A[KL2GvlyY]);}}if(N==1){int cTE1_r3A;int RZTsC2BF = rd_int();for(cTE1_r3A=(0);cTE1_r3A<(RZTsC2BF);cTE1_r3A++){rd(IND);rd(X);wt_L(X+1);wt_L('\n');}return 0;}ms.walloc(N, 1);mms.walloc(N);mms.setN(N);for(i=(0);i<(mms.N);i++){mms[i] = 0;}mms.build();for(i=(0);i<(N);i++){A[i] = -(A[i] - (N-2));}for(i=(0);i<(N);i++){ds += fDiv(A[i], N-1);ms.add(0, N-1-((moddw_L(A[i],(N-1)))), 1);mms.change(0, N-1-((moddw_L(A[i],(N-1)))), 1);}for(i=(0);i<(N);i++){ms.add(i,i+1,-(N-i));}for(i=(0);i<(N);i++){mms.change(i,i+1,-(N-i));}rd(Q);for(jZyWAPpY=(0);jZyWAPpY<(Q);jZyWAPpY++){long long res = 4611686016279904256LL;long long tmp;pair<long long,int> p;rd(IND);IND += (-1);rd(X);ds -= fDiv(A[IND], N-1);ms.add(0, N-1-((moddw_L(A[IND],(N-1)))), -1);mms.change(0, N-1-((moddw_L(A[IND],(N-1)))), -1);A[IND] = -(X - (N-2));ds += fDiv(A[IND], N-1);ms.add(0, N-1-((moddw_L(A[IND],(N-1)))), 1);mms.change(0, N-1-((moddw_L(A[IND],(N-1)))), 1);p = ms.getMin(0,N-1);tmp = ds - p.first;if(tmp > 0){val = ds;p.second = mms.max_right<f>(0);}chmin(res, p.second +max_L(-tmp, 0)* (N-1));wt_L(res);wt_L('\n');}return 0;}template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::malloc(int maxN, int once /*= 0*/){int i;for(i=1;i<maxN;i*=2){;}val = new SVAL[2*i];fun = new SFUN[i];dofun = new char[i];if(once){setN(maxN);}}template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::walloc(int maxN, int once /*= 0*/, void **mem /*= &wmem*/){int i;for(i=1;i<maxN;i*=2){;}walloc1d(&val, 2*i, mem);walloc1d(&fun, i, mem);walloc1d(&dofun, i, mem);if(once){setN(maxN);}}template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::free(void){delete [] val;delete [] fun;}template<class SVAL, class SFUN> SVAL& segtree_rh<SVAL, SFUN>::operator[](int i){return val[N+i];}template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::setN(int n, int zerofill /*= 1*/, int dobuild /*= 1*/){int i;for(i=1,logN=0;i<n;i*=2,logN++){;}trueN = n;N = i;if(dobuild){build();}}template<class SVAL, class SFUN> void segtree_rh<SVAL, SFUN>::build(void){int i;for(i=N-1;i;i--){val[i] = segtree_rh_merge(val[2*i], val[2*i+1]);}int tDCakidn = N;for(i=(1);i<(tDCakidn);i++){dofun[i] = 0;}}template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::push_one(int a){if(dofun[a]){if(2*a < N){if(dofun[2*a]){fun[2*a] = segtree_rh_compose(fun[a], fun[2*a]);}else{fun[2*a] = fun[a];dofun[2*a] = 1;}}val[2*a] = segtree_rh_apply(fun[a], val[2*a]);if(2*a+1 < N){if(dofun[2*a+1]){fun[2*a+1] = segtree_rh_compose(fun[a], fun[2*a+1]);}else{fun[2*a+1] = fun[a];dofun[2*a+1] = 1;}}val[2*a+1] = segtree_rh_apply(fun[a], val[2*a+1]);dofun[a] = 0;}}template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::push(int a){int i;for(i=logN;i;i--){push_one(a>>i);}}template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::build(int a){while(a > 1){a /= 2;val[a] = segtree_rh_merge(val[2*a], val[2*a+1]);if(dofun[a]){val[a] = segtree_rh_apply(fun[a], val[a]);}}}template<class SVAL, class SFUN> inline void segtree_rh<SVAL, SFUN>::change(int a, int b, SFUN f){int aa;int bb;if(a >= b){return;}aa = (a += N);bb = (b += N);push(a);push(b-1);if(a%2){val[a] = segtree_rh_apply(f, val[a]);a++;}if(b%2){b--;val[b] = segtree_rh_apply(f, val[b]);}a /= 2;b /= 2;while(a < b){if(a%2){val[a] = segtree_rh_apply(f, val[a]);if(dofun[a]){fun[a] = segtree_rh_compose(f, fun[a]);}else{fun[a] = f;dofun[a] = 1;}a++;}if(b%2){b--;val[b] = segtree_rh_apply(f, val[b]);if(dofun[b]){fun[b] = segtree_rh_compose(f, fun[b]);}else{fun[b] = f;dofun[b] = 1;}}a /= 2;b /= 2;}build(aa);build(bb-1);}template<class SVAL, class SFUN> inline SVAL segtree_rh<SVAL, SFUN>::get(int a, int b){SVAL res;SVAL tmp;int fga = 0;int fgb = 0;a += N;b += N;push(a);push(b-1);while(a < b){if(a%2){if(fga){res = segtree_rh_merge(res, val[a]);}else{res = val[a];fga = 1;}a++;}if(b%2){b--;if(fgb){tmp = segtree_rh_merge(val[b], tmp);}else{tmp = val[b];fgb = 1;}}a /= 2;b /= 2;}if(fga==1 && fgb==0){return res;}if(fga==0 && fgb==1){return tmp;}if(fga==1 && fgb==1){return segtree_rh_merge(res, tmp);}return res;}template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::max_right(int a, int mx){int fg = 0;int ta = a;int sz = 1;SVAL cur;SVAL tmp;if(a>=mx){return mx;}a += N;push(a);for(;;){while(a%2==0){a /= 2;sz *= 2;}if(ta + sz <= mx){if(fg==0){tmp = val[a];}else{tmp = segtree_rh_merge(cur, val[a]);}}if(ta + sz > mx || !f(tmp)){while(a < N){push_one(a);a *= 2;sz /= 2;if(ta + sz <= mx){if(fg==0){tmp = val[a];}else{tmp = segtree_rh_merge(cur, val[a]);}}if(ta + sz <= mx && f(tmp)){fg = 1;cur = tmp;a++;ta += sz;}}return a - N;}fg = 1;cur = tmp;if((a & (a+1)) == 0){break;}a++;ta += sz;}return mx;}template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::max_right(int a){return max_right<f>(a, trueN);}template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::min_left(int b, int mn){int fg = 0;int tb = b;int sz = 1;SVAL cur;SVAL tmp;if(b <= mn){return mn;}b += N;push(b-1);for(;;){while(b%2==0){b /= 2;sz *= 2;}if(tb - sz >= mn){if(fg==0){tmp = val[b-1];}else{tmp = segtree_rh_merge(val[b-1], cur);}}if(tb - sz < mn || !f(tmp)){while(b-1 < N){push_one(b-1);b *= 2;sz /= 2;if(tb - sz >= mn){if(fg==0){tmp = val[b-1];}else{tmp = segtree_rh_merge(val[b-1], cur);}}if(tb - sz >= mn && f(tmp)){fg = 1;cur = tmp;b--;tb -= sz;}}return b - N;}fg = 1;cur = tmp;b--;tb -= sz;if(tb <= mn){break;}}return mn;}template<class SVAL, class SFUN> template<bool (*f)(SVAL)> int segtree_rh<SVAL, SFUN>::min_left(int b){return min_left<f>(b, 0);}// cLay version 20210103-1 [bug fixed 2]// --- original code ---// //working_memory=300m//// ll segtree_rh_apply(ll f, ll a){ return a+f; }// ll segtree_rh_merge(ll a, ll b){ return min(a, b); }// ll segtree_rh_compose(ll f, ll g){ return f+g; }//// ll val;// bool f(ll a){// return a >= val;// }//// int N, A[2d5], Q, IND, X;// ll ds;// segtree<ll> ms;// segtree_rh<ll,ll> mms;// {// rd(N,A(N));//// if(N==1){// REP(rd_int()){// rd(IND,X);// wt(X+1);// }// return 0;// }//// ms.walloc(N, 1);// mms.walloc(N);// mms.setN(N);// rep(i,mms.N) mms[i] = 0;// mms.build();//// rep(i,N) A[i] = -(A[i] - (N-2));// rep(i,N){// ds += fDiv(A[i], N-1);// ms.add(0, N-1-(A[i]%%(N-1)), 1);// mms.change(0, N-1-(A[i]%%(N-1)), 1);// }// rep(i,N) ms.add(i,i+1,-(N-i));// rep(i,N) mms.change(i,i+1,-(N-i));//// rd(Q);// rep(Q){// ll res = ll_inf, tmp;// pair<ll,int> p;// rd(IND--, X);//// ds -= fDiv(A[IND], N-1);// ms.add(0, N-1-(A[IND]%%(N-1)), -1);// mms.change(0, N-1-(A[IND]%%(N-1)), -1);// A[IND] = -(X - (N-2));// ds += fDiv(A[IND], N-1);// ms.add(0, N-1-(A[IND]%%(N-1)), 1);// mms.change(0, N-1-(A[IND]%%(N-1)), 1);//// p = ms.getMin(0,N-1);// tmp = ds - p.first;// if(tmp > 0){// val = ds;// p.second = mms.max_right<f>(0);// }// res <?= p.second + max(-tmp, 0) * (N-1);// wt(res);// }// }