結果

問題 No.1394 Changing Problems
ユーザー leaf_1415
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 998244353
using namespace std;
typedef long long llint;
typedef long long ll;
typedef pair<llint, llint> P;
// range-add, range-min query
struct 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 element
return inf;
}
llint ope(llint a, llint b){ //operator
return 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0