結果
| 問題 | No.1394 Changing Problems |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2021-02-12 23:27:41 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,968 bytes |
| コンパイル時間 | 3,004 ms |
| コンパイル使用メモリ | 160,748 KB |
| 実行使用メモリ | 44,800 KB |
| 最終ジャッジ日時 | 2023-09-04 12:09:27 |
| 合計ジャッジ時間 | 6,989 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
8,756 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
ソースコード
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] <= 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[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) {
}
}