結果
問題 | No.1394 Changing Problems |
ユーザー |
![]() |
提出日時 | 2021-02-13 03:19:04 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,841 bytes |
コンパイル時間 | 884 ms |
コンパイル使用メモリ | 89,848 KB |
実行使用メモリ | 13,056 KB |
最終ジャッジ日時 | 2024-07-20 04:39:53 |
合計ジャッジ時間 | 20,687 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 WA * 5 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#include <complex>#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define reps(x, s) for(llint (x) = 0; (x) < (llint)(s).size(); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define all(x) (x).begin(),(x).end()#define outl(x) cout << x << endl#define SP << " " <<#define inf 1e18#define mod 998244353using namespace std;typedef long long llint;typedef long long ll;typedef pair<llint, llint> P;// range-add, range-min querystruct LazySegTree{int size;vector<llint> seg, delay;LazySegTree(){}LazySegTree(int size){this->size = size;seg.resize(1<<(size+1));delay.resize(1<<(size+1));}llint Ident(){ //identity elementreturn inf;}llint ope(llint a, llint b){ //operatorreturn min(a, b);}void init(){for(int i = 0; i < (1<<(size+1)); i++){seg[i] = Ident();delay[i] = 0; //}}void eval(int l, int r, int k) //{if(delay[k]){seg[k] += delay[k]; //総和クエリのときは区間幅を乗じる必要があるif(l < r){delay[k*2] += delay[k];delay[k*2+1] += delay[k];}delay[k] = 0;}}void update(int i, llint val){int l = 0, r = (1<<size)-1, k = 1;eval(l, r, k);for(int j = size-1; j >= 0; j--){k <<= 1;if(i & (1<<j)){k++;l = (l+r)/2+1;}else r = (l+r)/2;eval(l, r, k);}seg[i+(1<<size)] = val;l = i, r = i, k = i+(1<<size);for(int j = 0; j < size; j++){k /= 2, l &= ~(1<<j), r |= 1<<j;eval(l, (l+r)/2, k*2), eval((l+r)/2+1, r, k*2+1);seg[k] = ope(seg[k*2], seg[k*2+1]);}}void add(int a, int b, int k, int l, int r, llint val){eval(l, r, k);if(b < l || r < a) return;if(a <= l && r <= b){delay[k] += val; //eval(l, r, k);return;}add(a, b, k*2, l, (l+r)/2, val);add(a, b, k*2+1, (l+r)/2+1, r, val);seg[k] = ope(seg[k*2], seg[k*2+1]);}void add(int a, int b, llint val){if(a > b) return;add(a, b, 1, 0, (1<<size)-1, val);}llint query(int a, int b, int k, int l, int r){eval(l, r, k);if(b < l || r < a) return Ident();if(a <= l && r <= b) return seg[k];llint lval = query(a, b, k*2, l, (l+r)/2);llint rval = query(a, b, k*2+1, (l+r)/2+1, r);return ope(lval, rval);}llint query(int a, int b){if(a > b) return Ident();return query(a, b, 1, 0, (1<<size)-1);}};ll n, Q;ll a[200005];LazySegTree seg(18);P get(ll x){x = n-2-x;x += 2000000000 * (n-1);ll q = x / (n-1) - 2000000000, r = x % (n-1);return P(q, r);}ll find(ll x){ll ub = n-1, lb = -1, mid;while(ub-lb>1){mid = (ub+lb)/2;if(seg.query(0, mid) <= x) ub = mid;else lb = mid;}return ub;}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;rep(i, 1, n) cin >> a[i];cin >> Q;ll p, x;if(n == 1){rep(q, 1, Q){cin >> p >> x;a[p] = x;cout << max(0LL, a[1]-(n-2)) << "\n";}return 0;}seg.init();rep(i, 0, n-1) seg.update(i, i);ll b = 0;rep(i, 1, n){P res = get(a[i]);//cout << res.first << " " << res.second << endl;b += res.first, seg.add(n-1-res.second, n-1, -1);}rep(q, 1, Q){cin >> p >> x;P res = get(a[p]);b -= res.first, seg.add(n-1-res.second, n-1, 1);a[p] = x;res = get(a[p]);b += res.first, seg.add(n-1-res.second, n-1, -1);if(b >= 0){cout << 0 << endl;continue;}ll m = -seg.query(0, n-1);if(-b <= m) cout << find(b) << endl;else cout << (-b-m) * (n-1) + find(-m) << endl;}return 0;}