結果
問題 | No.1394 Changing Problems |
ユーザー |
👑 |
提出日時 | 2021-02-12 23:27:41 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,968 bytes |
コンパイル時間 | 1,928 ms |
コンパイル使用メモリ | 164,776 KB |
実行使用メモリ | 44,912 KB |
最終ジャッジ日時 | 2024-06-22 10:52:06 |
合計ジャッジ時間 | 7,258 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 2 TLE * 1 -- * 26 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;(unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }// T: monoid// op: T * T -> T// query(a, b): returns t_a ... t_{b-1}class SegmentTree(T, alias op) {import std.functional : binaryFun;alias opFun = binaryFun!op;const(T) idT;int n;T[] ts;this(int n_, const(T) idT) {this.idT = idT;for (n = 1; n < n_; n <<= 1) {}ts = new T[n << 1];ts[] = idT;}this(inout(T)[] ts_, const(T) idT) {this.idT = idT;const n_ = cast(int)(ts_.length);for (n = 1; n < n_; n <<= 1) {}ts = new T[n << 1];ts[0 .. n] = idT;ts[n .. n + n_] = ts_[];ts[n + n_ .. n << 1] = idT;build();}ref T at(int a) {return ts[n + a];}void build() {foreach_reverse (a; 1 .. n) ts[a] = opFun(ts[a << 1], ts[a << 1 | 1]);}void set(int a, const(T) val) {ts[a += n] = val;for (; a >>= 1; ) ts[a] = opFun(ts[a << 1], ts[a << 1 | 1]);}void mulL(int a, const(T) val) {set(a, opFun(val, ts[a + n]));}void mulR(int a, const(T) val) {set(a, opFun(ts[a + n], val));}T query(int a, int b) const {T prodL = idT, prodR = idT;for (a += n, b += n; a < b; a >>= 1, b >>= 1) {if (a & 1) prodL = opFun(prodL, ts[a++]);if (b & 1) prodR = opFun(ts[--b], prodR);}return opFun(prodL, prodR);}}enum INF = 10L^^18;struct T {long sum, mn, pos;}T opTT(T t0, T t1) {if (t0.mn <= t0.sum + t1.mn) {return T(t0.sum + t1.sum, t0.mn, t0.pos);} else {return T(t0.sum + t1.sum, t0.sum + t1.mn, t1.pos);}}enum ID_T = T(0, INF, -1);void main() {try {for (; ; ) {const N = readInt();auto A = new long[N];foreach (i; 0 .. N) {A[i] = readLong();}const Q = readInt();auto I = new int[Q];auto X = new long[Q];foreach (q; 0 .. Q) {I[q] = readInt() - 1;X[q] = readLong();}if (N == 1) {foreach (q; 0 .. Q) {/*X[q] + (-1) k <= -1*/writeln(max(X[q] + 1, 0));}} else {auto setB = new RedBlackTree!(long, "a < b", true);long sumB, sumQuot;auto seg = new SegmentTree!(T, opTT)(N - 1, ID_T);foreach (r; 0 .. N - 1) {seg.at(r) = T(1, 1, r);}void add(long a) {const b = a - (N - 2);setB.insert(b);sumB += b;int r = cast(int)(b % (N - 1));if (r < 0) r += (N - 1);sumQuot += (b - r) / (N - 1);T t = seg.at(r);t.sum -= 1;t.mn -= 1;seg.set(r, t);}void rem(long a) {const b = a - (N - 2);setB.removeKey(b);sumB -= b;int r = cast(int)(b % (N - 1));if (r < 0) r += (N - 1);sumQuot -= (b - r) / (N - 1);T t = seg.at(r);t.sum += 1;t.mn += 1;seg.set(r, t);}auto as = A.dup;foreach (i; 0 .. N) {add(as[i]);}foreach (q; 0 .. Q) {/*b[i] - k + (N - 1) x[i] <= 0k >= b[i]x[i] <= floor((k - b[i]) / (N - 1))OK if k >= \sum_i b[i] + N (N - 1)k = (N - 1) q + rN q - \sum_i floor(b[i] / (N - 1)) - #{i | (b[i] mod (N - 1)) > r} >= (N - 1) q + rq >= \sum_i floor(b[i] / (N - 1)) + N - 1 + (r + 1) - #{i | (b[i] mod (N - 1)) <= r}*/rem(as[I[q]]);as[I[q]] = X[q];add(as[I[q]]);long ans = INF;if (setB.back <= 0) {ans = 0;} else {const lb = setB.back;const r = cast(int)(lb % (N - 1));debug {writefln("lb = %s, r = %s", lb, r);}{const resL = seg.query(0, r);const res = seg.query(r, N - 1);long cost = sumQuot + N - 1 + (resL.sum + res.mn);chmax(cost, lb / (N - 1));chmin(ans, (N - 1) * cost + res.pos);}{const res = seg.query(0, N - 1);long cost = sumQuot + N - 1 + res.mn;chmax(cost, lb / (N - 1) + 1);chmin(ans, (N - 1) * cost + res.pos);}}writeln(ans);{//debug {long sum;foreach (i; 0 .. N) {const b = as[i] - (N - 2);assert(ans >= b);sum += (ans - b) / (N - 1);}assert(sum >= ans);}}debug {writeln("========");stdout.flush;}}}} catch (EOFException e) {}}