結果
問題 | No.1394 Changing Problems |
ユーザー |
![]() |
提出日時 | 2021-02-12 21:50:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 800 ms / 3,000 ms |
コード長 | 10,450 bytes |
コンパイル時間 | 2,400 ms |
コンパイル使用メモリ | 214,520 KB |
最終ジャッジ日時 | 2025-01-18 18:22:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;#define int ll#define rng(i,a,b) for(int i=int(a);i<int(b);i++)#define rep(i,b) rng(i,0,b)#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)#define per(i,b) gnr(i,0,b)#define pb push_back#define eb emplace_back#define a first#define b second#define bg begin()#define ed end()#define all(x) x.bg,x.ed#define si(x) int(x.size())#ifdef LOCAL#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl#else#define dmp(x) void(0)#endiftemplate<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}template<class t> using vc=vector<t>;template<class t> using vvc=vc<vc<t>>;using pi=pair<int,int>;using vi=vc<int>;template<class t,class u>ostream& operator<<(ostream& os,const pair<t,u>& p){return os<<"{"<<p.a<<","<<p.b<<"}";}template<class t> ostream& operator<<(ostream& os,const vc<t>& v){os<<"{";for(auto e:v)os<<e<<",";return os<<"}";}#define mp make_pair#define mt make_tuple#define one(x) memset(x,-1,sizeof(x))#define zero(x) memset(x,0,sizeof(x))#ifdef LOCALvoid dmpr(ostream&os){os<<endl;}template<class T,class... Args>void dmpr(ostream&os,const T&t,const Args&... args){os<<t<<" ";dmpr(os,args...);}#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)#else#define dmp2(...) void(0)#endifusing uint=unsigned;using ull=unsigned long long;template<class t,size_t n>ostream& operator<<(ostream&os,const array<t,n>&a){return os<<vc<t>(all(a));}template<int i,class T>void print_tuple(ostream&,const T&){}template<int i,class T,class H,class ...Args>void print_tuple(ostream&os,const T&t){if(i)os<<",";os<<get<i>(t);print_tuple<i+1,T,Args...>(os,t);}template<class ...Args>ostream& operator<<(ostream&os,const tuple<Args...>&t){os<<"{";print_tuple<0,tuple<Args...>,Args...>(os,t);return os<<"}";}template<class t>void print(t x,int suc=1){cout<<x;if(suc==1)cout<<"\n";if(suc==2)cout<<" ";}ll read(){ll i;cin>>i;return i;}vi readvi(int n,int off=0){vi v(n);rep(i,n)v[i]=read()+off;return v;}pi readpi(int off=0){int a,b;cin>>a>>b;return pi(a+off,b+off);}template<class t,class u>void print(const pair<t,u>&p,int suc=1){print(p.a,2);print(p.b,suc);}template<class T>void print(const vector<T>&v,int suc=1){rep(i,v.size())print(v[i],i==int(v.size())-1?suc:2);}string readString(){string s;cin>>s;return s;}template<class T>T sq(const T& t){return t*t;}//#define CAPITALvoid yes(bool ex=true){#ifdef CAPITALcout<<"YES"<<"\n";#elsecout<<"Yes"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}void no(bool ex=true){#ifdef CAPITALcout<<"NO"<<"\n";#elsecout<<"No"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}void possible(bool ex=true){#ifdef CAPITALcout<<"POSSIBLE"<<"\n";#elsecout<<"Possible"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}void impossible(bool ex=true){#ifdef CAPITALcout<<"IMPOSSIBLE"<<"\n";#elsecout<<"Impossible"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}constexpr ll ten(int n){return n==0?1:ten(n-1)*10;}const ll infLL=LLONG_MAX/3;#ifdef intconst int inf=infLL;#elseconst int inf=INT_MAX/2-100;#endifint topbit(signed t){return t==0?-1:31-__builtin_clz(t);}int topbit(ll t){return t==0?-1:63-__builtin_clzll(t);}int botbit(signed a){return a==0?32:__builtin_ctz(a);}int botbit(ll a){return a==0?64:__builtin_ctzll(a);}int popcount(signed t){return __builtin_popcount(t);}int popcount(ll t){return __builtin_popcountll(t);}bool ispow2(int i){return i&&(i&-i)==i;}ll mask(int i){return (ll(1)<<i)-1;}bool inc(int a,int b,int c){return a<=b&&b<=c;}template<class t> void mkuni(vc<t>&v){sort(all(v));v.erase(unique(all(v)),v.ed);}ll rand_int(ll l, ll r) { //[l, r]#ifdef LOCALstatic mt19937_64 gen;#elsestatic mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());#endifreturn uniform_int_distribution<ll>(l, r)(gen);}template<class t>void myshuffle(vc<t>&a){rep(i,si(a))swap(a[i],a[rand_int(0,i)]);}template<class t>int lwb(const vc<t>&v,const t&a){return lower_bound(all(v),a)-v.bg;}vvc<int> readGraph(int n,int m){vvc<int> g(n);rep(i,m){int a,b;cin>>a>>b;//sc.read(a,b);a--;b--;g[a].pb(b);g[b].pb(a);}return g;}vvc<int> readTree(int n){return readGraph(n,n-1);}//atcoder-library をまあまあコピーして使っている//N() が単位元//merge で片方が inactive のときはもう片方をそのまま返す,//といったときに,lazy の情報までコピーして渡さないようにする//get の最後の引数は単位元と口では言いつつ・・・?//たとえば min で最後の引数を 0 にしても 1 とかが返ってくることはある(一敗)//VERIFY://https://atcoder.jp/contests/practice2/tasks/practice2_ktemplate<class N>struct seglazy{vc<N> x;int L,s;seglazy(){}template<class T>seglazy(const vc<T>& a){int n=a.size();L=0;while((1<<L)<n)L++;s=1<<L;x.resize(s*2);rep(i,n)x[s+i]=N(a[i]);gnr(i,1,s)upd(i);}void upd(int i){x[i]=N::merge(x[i*2],x[i*2+1]);}void push(int i){x[i].push(x[i*2],x[i*2+1]);}N composite(int l,int r){assert(0<=l&&l<=r&&r<=s);if(l==r)return N();l+=s;r+=s;for (int i = L; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}N sml,smr;while (l < r) {if (l & 1) sml = N::merge(sml, x[l++]);if (r & 1) smr = N::merge(x[--r], smr);l >>= 1;r >>= 1;}return N::merge(sml, smr);}template<class F,class... Args>void ch(int l, int r, F f,Args&&... args) {assert(0<=l&&l<=r&&r<=s);if (l == r) return;l+=s;r+=s;for (int i = L; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while (l < r) {if (l & 1){(x[l++].*f)(forward<Args>(args)...);}if (r & 1){(x[--r].*f)(forward<Args>(args)...);}l >>= 1;r >>= 1;}l = l2;r = r2;}for (int i = 1; i <= L; i++) {if (((l >> i) << i) != l) upd(l >> i);if (((r >> i) << i) != r) upd((r - 1) >> i);}}N getall(){return x[1];}template <class F,class... Args>pair<int,N> max_right(int l,F f,Args&&... args){assert(0<=l&&l<=s);if(l==s)return mp(s,N());l+=s;for (int i = L; i >= 1; i--) push(l >> i);N sm;assert((sm.*f)(forward<Args>(args)...));do {while (l % 2 == 0) l >>= 1;if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){while (l < s) {push(l);l = (2 * l);N tmp=N::merge(sm,x[l]);if ((tmp.*f)(forward<Args>(args)...)) {sm = tmp;l++;}}return mp(l - s,sm);}sm = N::merge(sm, x[l]);l++;} while ((l & -l) != l);return mp(s,sm);}//XXI Opencup Krakow Mtemplate <class F,class... Args>pair<int,N> min_left(int r,F f,Args&&... args){assert(0<=r&&r<=s);if(r==0)return mp(0,N());r+=s;for (int i = L; i >= 1; i--) push((r - 1) >> i);N sm;do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {while (r < s) {push(r);r = (2 * r + 1);N tmp=N::merge(x[r],sm);if ((tmp.*f)(forward<Args>(args)...)) {sm = tmp;r--;}}return mp(r + 1 - s,sm);}sm = N::merge(x[r], sm);} while ((r & -r) != r);return mp(0,sm);}template<class F,class...Args>void point_change(int p,F f,Args&&...args){assert(0 <= p && p < s);p += s;for (int i = L; i >= 1; i--) push(p >> i);(x[p].*f)(forward<Args>(args)...);for (int i = 1; i <= L; i++) upd(p >> i);}N point_get(int p){assert(0 <= p && p < s);p += s;for (int i = L; i >= 1; i--) push(p >> i);return x[p];}void point_set(int p,N val){assert(0 <= p && p < s);p += s;for (int i = L; i >= 1; i--) push(p >> i);x[p]=val;for (int i = 1; i <= L; i++) upd(p >> i);}void enumerater(int l,int r,int i,int b,int e,vc<N>&dst){if(e<=l||r<=b)return;if(l+1==r){dst.pb(x[i]);return;}push(i);int m=(l+r)/2;enumerater(l,m,i*2,b,e,dst);enumerater(m,r,i*2+1,b,e,dst);}void enumerate(int b,int e,vc<N>&dst){assert(b<=e);return enumerater(0,s,1,b,e,dst);}};//Range add,maxstruct N{int lz,mx;N(int v=-inf):lz(0),mx(v){}void add(int v){mx+=v;lz+=v;}void push(N&x,N&y){x.add(lz);y.add(lz);lz=0;}static N merge(N x,N y){return N(max(x.getm(),y.getm()));}int getm(){return mx;}bool smaller(int v){return mx<v;}};void slv(){int n;cin>>n;vi a=readvi(n,2-n);int qnum;cin>>qnum;vc<pi> qs;rep(_,qnum){int i,x;cin>>i>>x;x-=n-2;qs.eb(i-1,x);}if(n==1){for(auto [i,x]:qs){a[i]=x;print(max<int>(a[i],0));}}else{multiset<int> s;s.insert(0);vi rw(n-1);rep(i,n-1)rw[i]=-i;seglazy<N> seg(rw);auto add=[&](int v){s.insert(v);v*=-1;int q=(v%(n-1)+(n-1))%(n-1);int p=(v-q)/(n-1);int len=n-1-q;seg.ch(0,len,&N::add,p);seg.ch(len,n-1,&N::add,p+1);};auto del=[&](int v){s.erase(s.find(v));v*=-1;int q=(v%(n-1)+(n-1))%(n-1);int p=(v-q)/(n-1);int len=n-1-q;seg.ch(0,len,&N::add,-p);seg.ch(len,n-1,&N::add,-(p+1));};auto sub=[&](int l,int r,int atl){if(l==r)return inf;int val=seg.composite(l,r).mx;if(val>=-atl)val=-atl;int idx=seg.max_right(l,&N::smaller,val).a;return -val*(n-1)+idx;};auto answer=[&](){int atl=*s.rbegin();int p=atl/(n-1),q=atl%(n-1);int ans=min(sub(0,q,p+1),sub(q,n-1,p));print(ans);};for(auto v:a)add(v);//answer();//dmp(a);for(auto [i,x]:qs){//dmp2(i,a[i],x);del(a[i]);add(a[i]=x);answer();}}}signed main(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);//int t;cin>>t;rep(_,t)slv();}