結果
| 問題 | No.1394 Changing Problems |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2021-02-13 00:18:27 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,275 bytes |
| コンパイル時間 | 1,694 ms |
| コンパイル使用メモリ | 160,956 KB |
| 実行使用メモリ | 56,576 KB |
| 最終ジャッジ日時 | 2023-09-04 12:09:59 |
| 合計ジャッジ時間 | 29,042 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 1 ms
4,380 KB |
| testcase_04 | AC | 1 ms
4,380 KB |
| testcase_05 | AC | 929 ms
53,704 KB |
| testcase_06 | AC | 1,063 ms
55,068 KB |
| testcase_07 | AC | 2 ms
4,380 KB |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | AC | 23 ms
4,544 KB |
| testcase_11 | AC | 24 ms
4,624 KB |
| testcase_12 | AC | 23 ms
4,560 KB |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 1,208 ms
56,416 KB |
| testcase_17 | AC | 1,213 ms
52,348 KB |
| testcase_18 | AC | 1,192 ms
52,804 KB |
| testcase_19 | AC | 1,200 ms
54,452 KB |
| testcase_20 | AC | 1,219 ms
53,612 KB |
| testcase_21 | AC | 1,163 ms
55,460 KB |
| testcase_22 | AC | 1,178 ms
52,076 KB |
| testcase_23 | AC | 1,206 ms
54,760 KB |
| testcase_24 | AC | 1,191 ms
52,076 KB |
| testcase_25 | AC | 1,223 ms
56,576 KB |
| testcase_26 | AC | 1,052 ms
54,384 KB |
| testcase_27 | AC | 1,029 ms
52,256 KB |
| testcase_28 | AC | 1,032 ms
54,964 KB |
| testcase_29 | AC | 922 ms
56,400 KB |
| testcase_30 | AC | 948 ms
52,076 KB |
| testcase_31 | AC | 935 ms
54,144 KB |
ソースコード
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);
}
// min b s.t. pred(prod of [a, b)) (or n + 1 if no such b)
// 0 <= a <= n
// assume pred(prod of [a, b)) is non-decreasing in b
int binarySearchR(int a, bool delegate(T) pred) const {
if (pred(idT)) return a;
if (a == n) return n + 1;
T prod = idT;
for (a += n; ; a >>= 1) {
if (a & 1) {
if (pred(opFun(prod, ts[a]))) {
for (; a < n; ) {
a <<= 1;
if (!pred(opFun(prod, ts[a]))) {
prod = opFun(prod, ts[a++]);
}
}
return a - n + 1;
}
prod = opFun(prod, ts[a++]);
if (!(a & a - 1)) return n + 1;
}
}
}
// max a s.t. pred(prod of [a, b)) (or -1 if no such a)
// 0 <= b <= n
// assume pred(prod of [a, b)) is non-increasing in a
int binarySearchL(int b, bool delegate(T) pred) const {
if (pred(idT)) return b;
if (b == 0) return -1;
T prod = idT;
for (b += n; ; b >>= 1) {
if ((b & 1) || b == 2) {
if (pred(opFun(prod, ts[b - 1]))) {
for (; b <= n; ) {
b <<= 1;
if (!pred(opFun(prod, ts[b - 1]))) {
prod = opFun(prod, ts[--b]);
}
}
return b - n - 1;
}
prod = opFun(prod, ts[--b]);
if (!(b & b - 1)) return -1;
}
}
}
}
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)(2 * (N - 1), ID_T);
foreach (r; 0 .. N - 1) {
seg.at(r) = T(1, 1, r);
seg.at((N - 1) + r) = T(1, 1, r);
}
seg.build;
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);
seg.set((N - 1) + 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);
seg.set((N - 1) + r, t);
}
auto as = A.dup;
foreach (i; 0 .. N) {
add(as[i]);
}
foreach (h; 0 .. Q) {
/*
b[i] - k + (N - 1) x[i] <= 0
k >= b[i]
x[i] <= floor((k - b[i]) / (N - 1))
OK if k >= \sum_i b[i] + N (N - 1)
k = (N - 1) q + r
N q - \sum_i floor(b[i] / (N - 1)) - #{i | (b[i] mod (N - 1)) > r} >= (N - 1) q + r
q >= \sum_i floor(b[i] / (N - 1)) + N - 1 + (r + 1) - #{i | (b[i] mod (N - 1)) <= r}
*/
rem(as[I[h]]);
as[I[h]] = X[h];
add(as[I[h]]);
long ans = INF;
if (setB.back <= 0) {
ans = 0;
} else {
const lb = setB.back;
const r = cast(int)(lb % (N - 1));
const q = (lb - r) / (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);
if (cost < q) {
const pos = seg.binarySearchR(r, (T t) {
return (q >= sumQuot + N - 1 + (resL.sum + t.mn));
}) - 1;
chmin(ans, (N - 1) * q + pos);
} else {
chmin(ans, (N - 1) * cost + res.pos);
}
}
{
const res = seg.query(0, N - 1);
long cost = sumQuot + N - 1 + res.mn;
if (cost < q + 1) {
const pos = seg.binarySearchR(0, (T t) {
return (q >= sumQuot + N - 1 + t.mn);
}) - 1;
chmin(ans, (N - 1) * (q + 1) + pos);
} else {
chmin(ans, (N - 1) * cost + res.pos);
}
}
}
writeln(ans);
debug {
for (long brt = max(setB.back, 0); ; ++brt) {
long sum;
foreach (i; 0 .. N) {
const b = as[i] - (N - 2);
sum += (brt - b) / (N - 1);
}
if (sum >= brt) {
if (brt != ans) {
writeln("as = ", as);
writeln("brt = ", brt);
writeln("ans = ", ans);
writeln("seg.ts = ", seg.ts);
}
assert(brt == ans);
break;
}
}
}
}
debug {
writeln("========");
stdout.flush;
}
}
}
} catch (EOFException e) {
}
}