Ghe gạo (Đề tự luyện HSG Tin quốc gia – Bài 4)
Đề bài
Ghe gạo. Dọc rạch có $N$ bến; bến $i$ có số $a_i$ ($a_i > 0$: bà con gửi $a_i$ kg gạo; $a_i < 0$: bến cần nhận $|a_i|$ kg). Ghe chở tối đa $C$ kg. Ghe đang chở $y$ kg ghé bến $i$ thì còn $\min(C, \max(0, y + a_i))$ kg; nếu $y + a_i < 0$ thì bến $i$ còn thiếu $-(y + a_i)$ kg. Có $Q$ kịch bản độc lập: kịch bản $j$ xuất phát với $x_j$ kg, ghé lần lượt các bến $l_j, l_j + 1, \ldots, r_j$. In tổng (trên mọi kịch bản) lượng gạo còn trên ghe khi kết thúc, và tổng lượng gạo còn thiếu.
Dữ liệu vào: dòng 1: $N$, $C$, $Q$; dòng 2: $a_1, \ldots, a_N$; $Q$ dòng tiếp: $l_j$, $r_j$, $x_j$. $1 \le N, Q \le 2 \cdot 10^5$, $1 \le C \le 10^{13}$, $|a_i| \le 10^7$, $0 \le x_j \le C$.
Kết quả: hai dòng: tổng lượng gạo còn trên ghe, tổng lượng gạo còn thiếu.
- Subtask 1 (10%): $N, Q \le 2000$.
- Subtask 2 (15%): $C \ge x_j + |a_1| + \ldots + |a_N|$ (ghe không bao giờ đầy).
- Subtask 3 (20%): $r_j = N$ với mọi $j$.
- Subtask 4 (25%): mỗi kịch bản có không quá $40$ bến phải để lại gạo hoặc bị thiếu.
- Subtask 5 (30%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.
7 7 3
-4 -7 4 -4 7 -3 -3
2 7 7
1 4 2
3 7 72
9Kịch bản 1: lượng gạo sau từng bến $0, 4, 0, 7, 4, 1$ — còn $1$, không thiếu. Kịch bản 2: thiếu $2$ ở bến 1, thiếu $7$ ở bến 2, rồi $4$, $0$ — còn $0$, thiếu $9$. Kịch bản 3: để lại $4$ ở bến 3, còn $3$, để lại $3$ ở bến 5, rồi $4$, $1$ — còn $1$. Tổng: $2$ và $9$.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Ghe gạoLời mở đầu
Đây là bài cuối, bài "phân loại" của đề. Mô phỏng thì ai cũng làm được, nhưng $N \cdot Q$ tới $4 \cdot 10^{10}$. Nhiều bạn sẽ nghĩ ngay tới cây phân đoạn: hàm "cộng $a_i$ rồi kẹp vào $[0, C]$" ghép với nhau vẫn là một hàm kẹp, nên lượng gạo cuối cùng tính được bằng cây phân đoạn. Nhưng bài còn hỏi tổng lượng thiếu — con số này không ghép được theo kiểu đó (nó phụ thuộc vào cả việc ghe có lúc bị đầy hay không). Ta cần một góc nhìn khác.
Gọi $P_i = a_1 + \ldots + a_i$ là tổng tiền tố. Ba nhận xét mở khóa bài:
- Khi chưa "chạm biên", mọi thứ là tổng tiền tố. Xuất phát ở bến $l$ với $x$ kg, nếu chưa lần nào ghe phải để lại gạo hay phát thiếu thì sau bến $i$ ghe có đúng $x + P_i - P_{l-1}$ kg.
- Lần chạm biên đầu tiên là bến $k \ge l$ đầu tiên có $x + P_k - P_{l-1} > C$ (ghe đầy, để lại phần dư) hoặc $< 0$ (ghe cạn, bến thiếu). Tức là $k$ đầu tiên mà $P_k$ thoát khỏi "cửa sổ" $[P_{l-1} - x,\; P_{l-1} - x + C]$.
- Sau một lần chạm biên, ghe "quên" quá khứ. Ngay sau bến $k$, ghe có đúng $C$ kg (nếu vừa đầy) hoặc $0$ kg (nếu vừa cạn), bất kể trước đó xuất phát thế nào. Vậy chỉ có $2N$ trạng thái "(bến $k$, đầy/cạn)", và từ mỗi trạng thái, lần chạm biên kế tiếp hoàn toàn xác định. Nối mỗi trạng thái tới trạng thái của lần chạm kế tiếp, ta được một rừng (cha luôn ở bến xa hơn).
Hình 1. Rừng các lần chạm biên của ví dụ. Mỗi kịch bản chỉ việc tìm lần chạm đầu tiên rồi "đi lên" trong rừng chừng nào còn ở bến $\le r$; lượng thiếu cộng dọc đường, lượng cuối $= C$ hoặc $0$ cộng $P_r - P_k$ (với $k$ là lần chạm cuối).
Vậy mỗi kịch bản gồm ba việc: (a) tìm lần chạm đầu tiên — bài toán "phần tử đầu tiên thoát khỏi cửa sổ"; (b) đi lên trong rừng tới lần chạm cuối cùng còn $\le r$ — nhảy nhị phân; (c) cộng lượng thiếu trên đường đi — tổng từ nút tới gốc, lấy hiệu. Các subtask được thiết kế để em ăn điểm dần dần từng mảnh.
Cách 1Mô phỏng – O(N · Q) · 10%
Làm đúng như đề: với mỗi kịch bản, đi qua từng bến, cộng $a_i$, nếu vượt $C$ thì kẹp về $C$, nếu âm thì cộng phần âm vào lượng thiếu và kẹp về $0$. Nhớ dùng long long: tổng lượng thiếu của một kịch bản có thể tới $2 \cdot 10^{12}$, và tổng trên mọi kịch bản tới cỡ $10^{18}$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q; long long C; cin >> n >> C >> q;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
long long sf = 0, ss = 0;
while (q--) {
int l, r; long long x; cin >> l >> r >> x;
for (int i = l; i <= r; i++) {
x += a[i];
if (x > C) x = C;
if (x < 0) { ss += -x; x = 0; }
}
sf += x;
}
cout << sf << "\n" << ss << "\n";
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); C = int(data[1]); q = int(data[2])
a = [int(x) for x in data[3:3 + n]]
sf = 0; ss = 0
p = 3 + n
for _ in range(q):
l = int(data[p]); r = int(data[p + 1]); x = int(data[p + 2]); p += 3
for i in range(l - 1, r): # mo phong tung ben
x += a[i]
if x > C:
x = C
elif x < 0:
ss -= x; x = 0
sf += x
print(sf)
print(ss)
main()Cách 2Ghe không bao giờ đầy: tổng tiền tố nhỏ nhất – O((N + Q) log N) · 25%
Khi $C$ rất lớn, chỉ còn "kẹp dưới" ở $0$. Lượng gạo sau bến $r$ là lớn nhất trong hai khả năng: không lần nào cạn ($x + P_r - P_{l-1}$), hoặc lần cạn cuối cùng ở bến $k \in [l, r]$ — khi đó ghe từ $0$ kg sau bến $k$ đi tiếp được $P_r - P_k$. Gộp lại:
$$\text{cuối} = P_r - \min\left(P_{l-1} - x,\; \min_{l \le k \le r} P_k\right).$$
Vì không bao giờ phải để lại gạo, toàn bộ phần "chênh" giữa lượng cuối và $x + P_r - P_{l-1}$ chính là gạo được "bù" vào chỗ thiếu: thiếu $=$ cuối $- (x + P_r - P_{l-1})$. Phần $\min P_k$ trên đoạn lấy bằng bảng thưa (sparse table) trong $O(1)$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, q; ll C; scanf("%d %lld %d", &n, &C, &q);
vector<ll> a(n + 1), P(n + 1, 0);
ll sumAbs = 0;
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); P[i] = P[i - 1] + a[i]; sumAbs += llabs(a[i]); }
vector<int> L(q), R(q); vector<ll> X(q); ll maxX = 0;
for (int j = 0; j < q; j++) { scanf("%d %d %lld", &L[j], &R[j], &X[j]); maxX = max(maxX, X[j]); }
ll sf = 0, ss = 0;
if (C >= maxX + sumAbs) { // Cach 2: ghe khong bao gio day
int LG = __lg(n) + 1;
vector<vector<ll>> mn(LG + 1, vector<ll>(n + 2)); // bang thua: min P tren doan
for (int i = 1; i <= n; i++) mn[0][i] = P[i];
for (int k = 1; k <= LG; k++)
for (int i = 1; i + (1 << k) - 1 <= n; i++)
mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
for (int j = 0; j < q; j++) {
int l = L[j], r = R[j], k = __lg(r - l + 1);
ll m = min(mn[k][l], mn[k][r - (1 << k) + 1]);
ll fin = P[r] - min(P[l - 1] - X[j], m); // = max(x + P[r]-P[l-1], P[r]-P[k])
sf += fin; ss += fin - (X[j] + P[r] - P[l - 1]);
}
} else { // Cach 1: mo phong
for (int j = 0; j < q; j++) {
ll x = X[j];
for (int i = L[j]; i <= R[j]; i++) {
x += a[i];
if (x > C) x = C;
if (x < 0) { ss -= x; x = 0; }
}
sf += x;
}
}
printf("%lld\n%lld\n", sf, ss);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); C = int(data[1]); q = int(data[2])
a = [int(x) for x in data[3:3 + n]]
P = [0] * (n + 1)
for i in range(n):
P[i + 1] = P[i] + a[i]
b = 3 + n
L = [int(x) for x in data[b:b + 3 * q:3]]
R = [int(x) for x in data[b + 1:b + 3 * q:3]]
X = [int(x) for x in data[b + 2:b + 3 * q:3]]
sf = 0; ss = 0
if C >= max(X) + sum(abs(v) for v in a): # Cach 2: ghe khong bao gio day
mn = [P[:]] # bang thua: min P tren doan
k = 1
while (1 << k) <= n:
prev = mn[-1]; h = 1 << (k - 1)
mn.append([min(prev[i], prev[i + h]) for i in range(n + 1 - (1 << k) + 1)])
k += 1
for j in range(q):
l = L[j]; r = R[j]; k = (r - l + 1).bit_length() - 1
t = mn[k]; m = min(t[l], t[r - (1 << k) + 1])
fin = P[r] - min(P[l - 1] - X[j], m)
sf += fin; ss += fin - (X[j] + P[r] - P[l - 1])
else: # Cach 1: mo phong
for j in range(q):
x = X[j]
for i in range(L[j] - 1, R[j]):
x += a[i]
if x > C:
x = C
elif x < 0:
ss -= x; x = 0
sf += x
print(sf)
print(ss)
main()Cách 3Mọi kịch bản đi tới bến N: tìm lần chạm đầu tiên, rồi đi tới gốc – O((N + Q) log N) · 45%
Tìm lần chạm đầu tiên. Xuất phát ở bến $s$ (tức là trước bến $s$ có $y$ kg, mốc $P_{s-1}$), ta cần bến $k \ge s$ đầu tiên có $P_k > hi$ hoặc $P_k < lo$ với $hi = P_{s-1} + C - y$, $lo = P_{s-1} - y$. Dựng bảng thưa mx[j][i], mn[j][i] là max, min của $P$ trên đoạn $[i, i + 2^j)$, rồi "nhảy lũy thừa 2": thử $j$ từ lớn tới nhỏ, nếu cả đoạn $[pos, pos + 2^j)$ vẫn nằm trong $[lo, hi]$ thì nhảy qua cả đoạn. Sau vòng lặp, $pos$ chính là bến chạm biên đầu tiên ($pos = N + 1$ nếu không có). Nếu $P_{pos} > hi$ là chạm trần (ghe đầy), ngược lại là chạm đáy, thiếu $lo - P_{pos}$.
Từ một trạng thái đi tới bến N. Gọi fin[k][t] và sh[k][t] là lượng gạo khi tới bến $N$ và tổng lượng thiếu, nếu ngay sau bến $k$ ghe đang cạn ($t = 0$) hay đầy ($t = 1$). Tìm lần chạm kế tiếp $e$ từ trạng thái đó: nếu không có thì fin = $v + P_N - P_k$, sh = 0; nếu có thì lấy kết quả của trạng thái tại $e$ (cộng thêm lượng thiếu ở $e$). Vì $e > k$ nên tính $k$ từ $N$ về $1$. Mỗi kịch bản: tìm lần chạm đầu tiên rồi tra bảng.
Mô phỏng dưới đây cho em thấy cách "nhảy" từ lần chạm này sang lần chạm kế tiếp: mỗi bước là một cửa sổ $[lo, hi]$ mới, và ta chỉ cần biết bến đầu tiên mà $P$ thoát khỏi cửa sổ.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, LG;
ll C;
vector<ll> a, P;
vector<vector<ll>> mx, mn; // bang thua max / min cua P
// ben dau tien k >= s co P[k] > hi hoac P[k] < lo (n + 1 neu khong co)
int firstExit(int s, ll hi, ll lo) {
int pos = s;
for (int k = LG; k >= 0; k--)
if (pos + (1 << k) - 1 <= n && mx[k][pos] <= hi && mn[k][pos] >= lo) pos += 1 << k;
return pos;
}
int main() {
scanf("%d %lld %d", &n, &C, &q);
a.assign(n + 1, 0); P.assign(n + 1, 0);
ll sumAbs = 0;
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); P[i] = P[i - 1] + a[i]; sumAbs += llabs(a[i]); }
vector<int> L(q), R(q); vector<ll> X(q); ll maxX = 0; bool allN = true;
for (int j = 0; j < q; j++) { scanf("%d %d %lld", &L[j], &R[j], &X[j]); maxX = max(maxX, X[j]); allN &= R[j] == n; }
LG = __lg(n);
mx.assign(LG + 1, vector<ll>(n + 2)); mn.assign(LG + 1, vector<ll>(n + 2));
for (int i = 1; i <= n; i++) mx[0][i] = mn[0][i] = P[i];
for (int k = 1; k <= LG; k++)
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
}
ll sf = 0, ss = 0;
if (allN) { // Cach 3: moi chuyen di den ben N
// fin[k][t], sh[k][t]: xuat phat ngay sau ben k voi ghe can (t = 0) / day (t = 1), di den ben N
vector<array<ll, 2>> fin(n + 1), sh(n + 1);
for (int k = n; k >= 1; k--)
for (int t = 0; t < 2; t++) {
ll v = t ? C : 0;
int e = firstExit(k + 1, P[k] + C - v, P[k] - v);
if (e > n) { fin[k][t] = v + P[n] - P[k]; sh[k][t] = 0; continue; }
int t2 = P[e] > P[k] + C - v; // 1: cham tran, 0: cham can
fin[k][t] = fin[e][t2];
sh[k][t] = (t2 ? 0 : P[k] - v - P[e]) + sh[e][t2];
}
for (int j = 0; j < q; j++) {
int l = L[j]; ll x = X[j];
int e = firstExit(l, P[l - 1] + C - x, P[l - 1] - x);
if (e > n) { sf += x + P[n] - P[l - 1]; continue; }
int t2 = P[e] > P[l - 1] + C - x;
sf += fin[e][t2];
ss += (t2 ? 0 : P[l - 1] - x - P[e]) + sh[e][t2];
}
} else if (C >= maxX + sumAbs) { // Cach 2: ghe khong bao gio day
for (int j = 0; j < q; j++) {
int l = L[j], r = R[j], k = __lg(r - l + 1);
ll m = min(mn[k][l], mn[k][r - (1 << k) + 1]);
ll f = P[r] - min(P[l - 1] - X[j], m);
sf += f; ss += f - (X[j] + P[r] - P[l - 1]);
}
} else { // Cach 1: mo phong
for (int j = 0; j < q; j++) {
ll x = X[j];
for (int i = L[j]; i <= R[j]; i++) {
x += a[i];
if (x > C) x = C;
if (x < 0) { ss -= x; x = 0; }
}
sf += x;
}
}
printf("%lld\n%lld\n", sf, ss);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); C = int(data[1]); q = int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
P = [0] * (n + 1)
for i in range(1, n + 1):
P[i] = P[i - 1] + a[i]
b = 3 + n
L = [int(x) for x in data[b:b + 3 * q:3]]
R = [int(x) for x in data[b + 1:b + 3 * q:3]]
X = [int(x) for x in data[b + 2:b + 3 * q:3]]
mx = [P[:]]; mn = [P[:]] # bang thua max / min cua P
k = 1
while (1 << k) <= n:
pm = mx[-1]; pn = mn[-1]; h = 1 << (k - 1); m = n + 2 - (1 << k)
mx.append([max(pm[i], pm[i + h]) for i in range(m)])
mn.append([min(pn[i], pn[i + h]) for i in range(m)])
k += 1
LG = len(mx) - 1
def first_exit(s, hi, lo): # ben dau tien k >= s co P[k] > hi hoac P[k] < lo
pos = s
for k in range(LG, -1, -1):
if pos + (1 << k) - 1 <= n and mx[k][pos] <= hi and mn[k][pos] >= lo:
pos += 1 << k
return pos
sf = 0; ss = 0
if all(r == n for r in R): # Cach 3: moi chuyen di den ben N
fin = [[0, 0] for _ in range(n + 1)]; sh = [[0, 0] for _ in range(n + 1)]
for k in range(n, 0, -1):
for t in (0, 1):
v = C if t else 0
e = first_exit(k + 1, P[k] + C - v, P[k] - v)
if e > n:
fin[k][t] = v + P[n] - P[k]
continue
t2 = 1 if P[e] > P[k] + C - v else 0
fin[k][t] = fin[e][t2]
sh[k][t] = (0 if t2 else P[k] - v - P[e]) + sh[e][t2]
for j in range(q):
l = L[j]; x = X[j]
e = first_exit(l, P[l - 1] + C - x, P[l - 1] - x)
if e > n:
sf += x + P[n] - P[l - 1]
continue
t2 = 1 if P[e] > P[l - 1] + C - x else 0
sf += fin[e][t2]
ss += (0 if t2 else P[l - 1] - x - P[e]) + sh[e][t2]
elif C >= max(X) + sum(abs(v) for v in a): # Cach 2: ghe khong bao gio day
for j in range(q):
l = L[j]; r = R[j]; k = (r - l + 1).bit_length() - 1
m = min(mn[k][l], mn[k][r - (1 << k) + 1])
f = P[r] - min(P[l - 1] - X[j], m)
sf += f; ss += f - (X[j] + P[r] - P[l - 1])
else: # Cach 1: mo phong
for j in range(q):
x = X[j]
for i in range(L[j], R[j] + 1):
x += a[i]
if x > C:
x = C
elif x < 0:
ss -= x; x = 0
sf += x
print(sf)
print(ss)
main()fin/sh "đi một mạch" tới bến $N$. Khi $r < N$ ta phải dừng ở lần chạm cuối cùng còn $\le r$ — và đó chính là chỗ phải nhảy nhị phân ở Cách 5.Cách 4Nhảy từ lần chạm này sang lần chạm kế tiếp – O(Q · H · log N) · 70%
Nếu mỗi kịch bản chỉ có ít lần chạm biên ($H \le 40$), ta làm đúng như mô phỏng ở trên: tìm lần chạm đầu tiên, cập nhật ghe thành $C$ hoặc $0$ và mốc $P$ mới, rồi lại tìm lần chạm kế tiếp, cho tới khi lần chạm vượt quá $r$. Mỗi lần tìm tốn $O(\log N)$ nhờ bảng thưa. Code dưới đây vẫn giữ Cách 2 và Cách 3 cho các subtask tương ứng.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, LG;
ll C;
vector<ll> a, P;
vector<vector<ll>> mx, mn; // bang thua max / min cua P
// ben dau tien k >= s co P[k] > hi hoac P[k] < lo (n + 1 neu khong co)
int firstExit(int s, ll hi, ll lo) {
int pos = s;
for (int k = LG; k >= 0; k--)
if (pos + (1 << k) - 1 <= n && mx[k][pos] <= hi && mn[k][pos] >= lo) pos += 1 << k;
return pos;
}
int main() {
scanf("%d %lld %d", &n, &C, &q);
a.assign(n + 1, 0); P.assign(n + 1, 0);
ll sumAbs = 0;
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); P[i] = P[i - 1] + a[i]; sumAbs += llabs(a[i]); }
vector<int> L(q), R(q); vector<ll> X(q); ll maxX = 0; bool allN = true;
for (int j = 0; j < q; j++) { scanf("%d %d %lld", &L[j], &R[j], &X[j]); maxX = max(maxX, X[j]); allN &= R[j] == n; }
LG = __lg(n);
mx.assign(LG + 1, vector<ll>(n + 2)); mn.assign(LG + 1, vector<ll>(n + 2));
for (int i = 1; i <= n; i++) mx[0][i] = mn[0][i] = P[i];
for (int k = 1; k <= LG; k++)
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
}
ll sf = 0, ss = 0;
if (allN) { // Cach 3: moi chuyen di den ben N
// fin[k][t], sh[k][t]: xuat phat ngay sau ben k voi ghe can (t = 0) / day (t = 1), di den ben N
vector<array<ll, 2>> fin(n + 1), sh(n + 1);
for (int k = n; k >= 1; k--)
for (int t = 0; t < 2; t++) {
ll v = t ? C : 0;
int e = firstExit(k + 1, P[k] + C - v, P[k] - v);
if (e > n) { fin[k][t] = v + P[n] - P[k]; sh[k][t] = 0; continue; }
int t2 = P[e] > P[k] + C - v; // 1: cham tran, 0: cham can
fin[k][t] = fin[e][t2];
sh[k][t] = (t2 ? 0 : P[k] - v - P[e]) + sh[e][t2];
}
for (int j = 0; j < q; j++) {
int l = L[j]; ll x = X[j];
int e = firstExit(l, P[l - 1] + C - x, P[l - 1] - x);
if (e > n) { sf += x + P[n] - P[l - 1]; continue; }
int t2 = P[e] > P[l - 1] + C - x;
sf += fin[e][t2];
ss += (t2 ? 0 : P[l - 1] - x - P[e]) + sh[e][t2];
}
} else if (C >= maxX + sumAbs) { // Cach 2: ghe khong bao gio day
for (int j = 0; j < q; j++) {
int l = L[j], r = R[j], k = __lg(r - l + 1);
ll m = min(mn[k][l], mn[k][r - (1 << k) + 1]);
ll f = P[r] - min(P[l - 1] - X[j], m);
sf += f; ss += f - (X[j] + P[r] - P[l - 1]);
}
} else { // Cach 4: nhay tu lan cham bien nay sang lan cham bien ke tiep
for (int j = 0; j < q; j++) {
int pos = L[j], r = R[j];
ll cur = X[j], base = P[pos - 1]; // luong gao hien tai = cur + P[i] - base
while (true) {
int e = firstExit(pos, base + C - cur, base - cur);
if (e > r) break;
if (P[e] > base + C - cur) cur = C;
else { ss += base - cur - P[e]; cur = 0; }
base = P[e]; pos = e + 1;
}
sf += cur + P[r] - base;
}
}
printf("%lld\n%lld\n", sf, ss);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); C = int(data[1]); q = int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
P = [0] * (n + 1)
for i in range(1, n + 1):
P[i] = P[i - 1] + a[i]
b = 3 + n
L = [int(x) for x in data[b:b + 3 * q:3]]
R = [int(x) for x in data[b + 1:b + 3 * q:3]]
X = [int(x) for x in data[b + 2:b + 3 * q:3]]
mx = [P[:]]; mn = [P[:]] # bang thua max / min cua P
k = 1
while (1 << k) <= n:
pm = mx[-1]; pn = mn[-1]; h = 1 << (k - 1); m = n + 2 - (1 << k)
mx.append([max(pm[i], pm[i + h]) for i in range(m)])
mn.append([min(pn[i], pn[i + h]) for i in range(m)])
k += 1
LG = len(mx) - 1
def first_exit(s, hi, lo): # ben dau tien k >= s co P[k] > hi hoac P[k] < lo
pos = s
for k in range(LG, -1, -1):
if pos + (1 << k) - 1 <= n and mx[k][pos] <= hi and mn[k][pos] >= lo:
pos += 1 << k
return pos
sf = 0; ss = 0
if all(r == n for r in R): # Cach 3: moi chuyen di den ben N
fin = [[0, 0] for _ in range(n + 1)]; sh = [[0, 0] for _ in range(n + 1)]
for k in range(n, 0, -1):
for t in (0, 1):
v = C if t else 0
e = first_exit(k + 1, P[k] + C - v, P[k] - v)
if e > n:
fin[k][t] = v + P[n] - P[k]
continue
t2 = 1 if P[e] > P[k] + C - v else 0
fin[k][t] = fin[e][t2]
sh[k][t] = (0 if t2 else P[k] - v - P[e]) + sh[e][t2]
for j in range(q):
l = L[j]; x = X[j]
e = first_exit(l, P[l - 1] + C - x, P[l - 1] - x)
if e > n:
sf += x + P[n] - P[l - 1]
continue
t2 = 1 if P[e] > P[l - 1] + C - x else 0
sf += fin[e][t2]
ss += (0 if t2 else P[l - 1] - x - P[e]) + sh[e][t2]
elif C >= max(X) + sum(abs(v) for v in a): # Cach 2: ghe khong bao gio day
for j in range(q):
l = L[j]; r = R[j]; k = (r - l + 1).bit_length() - 1
m = min(mn[k][l], mn[k][r - (1 << k) + 1])
f = P[r] - min(P[l - 1] - X[j], m)
sf += f; ss += f - (X[j] + P[r] - P[l - 1])
else: # Cach 4: nhay tu lan cham bien nay sang lan ke tiep
for j in range(q):
pos = L[j]; r = R[j]
cur = X[j]; base = P[pos - 1] # luong gao hien tai = cur + P[i] - base
while True:
e = first_exit(pos, base + C - cur, base - cur)
if e > r:
break
if P[e] > base + C - cur:
cur = C
else:
ss += base - cur - P[e]; cur = 0
base = P[e]; pos = e + 1
sf += cur + P[r] - base
print(sf)
print(ss)
main()Ở Subtask 5, $C$ nhỏ thì gần như bến nào cũng là một lần chạm, $H$ lên tới $10^5$ — Cách 4 quá giờ. Phải nhảy nhiều lần chạm một lúc.
Cách 5Rừng các lần chạm + nhảy nhị phân – O((N + Q) log N) · 100%
Ghép hai ý của Cách 3 và Cách 4:
- Mỗi trạng thái "(bến $k$, cạn/đầy)" là một nút; đánh số nút $2k$ (cạn) và $2k + 1$ (đầy), nút $0$ nghĩa là "không có".
up[0][u]là nút của lần chạm kế tiếp (cha),sh[u]là tổng lượng thiếu từ $u$ đi lên tới gốc. - Mỗi kịch bản: tìm nút $u$ của lần chạm đầu tiên. Nếu không có hoặc ở bến $> r$: ghe không chạm biên, cuối $= x + P_r - P_{l-1}$. Ngược lại nhảy nhị phân từ $u$ lên nút $v$ xa nhất còn ở bến $\le r$ (bến của các nút tăng dần khi đi lên, nên điều kiện "còn $\le r$" đúng một đoạn liên tiếp từ $u$). Lượng thiếu $= s_0 + sh[u] - sh[v]$ ($s_0$ là lượng thiếu ở lần chạm đầu tiên), lượng cuối $=$ ($C$ nếu $v$ là nút đầy, $0$ nếu cạn) $+ P_r - P_{bến(v)}$.
Tìm lần chạm cho nhanh (và hợp với Python). Mọi điểm xuất phát đều biết trước (các nút và các kịch bản), nên thay vì bảng thưa ta quét $s$ từ $N$ về $1$ và giữ hai ngăn xếp đơn điệu của $P[s..N]$: mx là chuỗi "bến đầu tiên có $P$ lớn hơn" bắt đầu từ $s$ (giá trị $P$ tăng dần từ đỉnh xuống đáy), mn tương tự với "nhỏ hơn". Bến đầu tiên có $P > hi$ chắc chắn nằm trong chuỗi mx (nó là một kỷ lục mới), và các phần tử có $P > hi$ tạo thành một đoạn ở đáy ngăn xếp ⇒ chặt nhị phân để lấy phần tử gần đỉnh nhất của đoạn đó. Mỗi lần tìm $O(\log N)$, bộ nhớ chỉ $O(N)$ — với Python ta dùng luôn bisect.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LOG = 19;
int n, q;
ll C;
vector<ll> P;
// Quet s tu n ve 1, giu hai ngan xep don dieu cua P[s..n]:
// mx: chuoi "phan tu lon hon dau tien" (P tang dan tu dinh xuong day),
// mn: chuoi "phan tu nho hon dau tien" (P giam dan tu dinh xuong day).
vector<int> mx, mn;
// ben dau tien k >= s co P[k] > hi hoac P[k] < lo; tra ve 2k+1 (day) / 2k (can) / 0 (khong co)
int firstHit(ll hi, ll lo) {
int a = n + 1, b = n + 1;
int L = 0, R = mx.size(); // tim phan tu gan dinh nhat co P > hi
while (L < R) { int M = (L + R) / 2; if (P[mx[M]] > hi) L = M + 1; else R = M; }
if (L > 0) a = mx[L - 1];
L = 0; R = mn.size(); // tim phan tu gan dinh nhat co P < lo
while (L < R) { int M = (L + R) / 2; if (P[mn[M]] < lo) L = M + 1; else R = M; }
if (L > 0) b = mn[L - 1];
if (a > n && b > n) return 0;
return a < b ? 2 * a + 1 : 2 * b;
}
int main() {
scanf("%d %lld %d", &n, &C, &q);
P.assign(n + 1, 0);
for (int i = 1; i <= n; i++) { ll a; scanf("%lld", &a); P[i] = P[i - 1] + a; }
vector<int> ql(q), qr(q); vector<ll> qx(q);
vector<vector<int>> at(n + 2);
for (int j = 0; j < q; j++) { scanf("%d %d %lld", &ql[j], &qr[j], &qx[j]); at[ql[j]].push_back(j); }
// nut 2k: ghe can (0 kg) ngay sau ben k; nut 2k+1: ghe day (C kg) ngay sau ben k
int M = 2 * n + 2;
vector<vector<int>> up(LOG, vector<int>(M, 0));
vector<ll> sh(M, 0); // tong luong thieu tu nut den goc cua no
vector<int> hit(q);
for (int s = n; s >= 1; s--) {
while (!mx.empty() && P[mx.back()] <= P[s]) mx.pop_back();
mx.push_back(s);
while (!mn.empty() && P[mn.back()] >= P[s]) mn.pop_back();
mn.push_back(s);
for (int t = 0; t < 2 && s >= 2; t++) { // hai nut cua ben s - 1
int u = 2 * (s - 1) + t; ll v = t ? C : 0;
int p = firstHit(P[s - 1] + C - v, P[s - 1] - v);
up[0][u] = p;
if (p) sh[u] = (p & 1 ? 0 : P[s - 1] - v - P[p / 2]) + sh[p];
}
for (int j : at[s]) hit[j] = firstHit(P[s - 1] + C - qx[j], P[s - 1] - qx[j]);
}
for (int k = 1; k < LOG; k++)
for (int u = 0; u < M; u++) up[k][u] = up[k - 1][up[k - 1][u]];
ll sumF = 0, sumS = 0;
for (int j = 0; j < q; j++) {
int l = ql[j], r = qr[j], u = hit[j]; ll x = qx[j];
if (u == 0 || u / 2 > r) { sumF += x + P[r] - P[l - 1]; continue; }
ll s0 = (u & 1) ? 0 : P[l - 1] - x - P[u / 2]; // thieu o lan cham dau tien
int v = u;
for (int k = LOG - 1; k >= 0; k--) {
int w = up[k][v];
if (w && w / 2 <= r) v = w;
}
sumS += s0 + sh[u] - sh[v];
sumF += (v & 1 ? C : 0) + P[r] - P[v / 2];
}
printf("%lld\n%lld\n", sumF, sumS);
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); C = int(data[1]); q = int(data[2])
P = [0] * (n + 1)
acc = 0
for i in range(1, n + 1):
acc += int(data[2 + i]); P[i] = acc
b = 3 + n
ql = [int(x) for x in data[b:b + 3 * q:3]]
qr = [int(x) for x in data[b + 1:b + 3 * q:3]]
qx = [int(x) for x in data[b + 2:b + 3 * q:3]]
head = [-1] * (n + 2); nxt = [-1] * q # gom cac chuyen theo ben xuat phat
for j in range(q):
nxt[j] = head[ql[j]]; head[ql[j]] = j
M = 2 * n + 2
up0 = [0] * M # nut 2k: ghe can sau ben k; nut 2k+1: ghe day sau ben k
sh = [0] * M # tong luong thieu tu nut den goc
hit = [0] * q
mx = []; mxv = [] # ngan xep don dieu (P tang dan tu dinh xuong day); mxv = -P
mn = []; mnv = [] # ngan xep don dieu (P giam dan tu dinh xuong day); mnv = P
N1 = n + 1
for s in range(n, 0, -1):
ps = P[s]
while mx and mxv[-1] >= -ps:
mx.pop(); mxv.pop()
mx.append(s); mxv.append(-ps)
while mn and mnv[-1] >= ps:
mn.pop(); mnv.pop()
mn.append(s); mnv.append(ps)
p0 = P[s - 1]
if s >= 2:
for t in (0, 1):
v = C if t else 0
hi = p0 + C - v; lo = p0 - v
k = bisect_left(mxv, -hi); a = mx[k - 1] if k else N1
k = bisect_left(mnv, lo); bb = mn[k - 1] if k else N1
if a < bb:
p = 2 * a + 1; up0[2 * s - 2 + t] = p; sh[2 * s - 2 + t] = sh[p]
elif bb < a:
p = 2 * bb; up0[2 * s - 2 + t] = p; sh[2 * s - 2 + t] = lo - P[bb] + sh[p]
j = head[s]
while j != -1:
x = qx[j]
hi = p0 + C - x; lo = p0 - x
k = bisect_left(mxv, -hi); a = mx[k - 1] if k else N1
k = bisect_left(mnv, lo); bb = mn[k - 1] if k else N1
if a < bb:
hit[j] = 2 * a + 1
elif bb < a:
hit[j] = 2 * bb
j = nxt[j]
ups = [up0]
LOG = max(1, (n + 1).bit_length())
for _ in range(LOG - 1):
prev = ups[-1]
ups.append([prev[u] for u in prev])
ups.reverse()
sumF = 0; sumS = 0
for j in range(q):
l = ql[j]; r = qr[j]; u = hit[j]; x = qx[j]
if u == 0 or (u >> 1) > r:
sumF += x + P[r] - P[l - 1]
continue
s0 = 0 if u & 1 else P[l - 1] - x - P[u >> 1]
v = u
for lv in ups:
w = lv[v]
if w and (w >> 1) <= r:
v = w
sumS += s0 + sh[u] - sh[v]
sumF += (C if v & 1 else 0) + P[r] - P[v >> 1]
sys.stdout.write("%d\n%d\n" % (sumF, sumS))
main()- Dùng "hàm kẹp ghép được" để tính lượng cuối rồi suy ra lượng thiếu $= \max(0, \text{cuối} - x - \sum a)$: chỉ đúng khi kịch bản không có lần nào để lại gạo. Ví dụ trong đề tình cờ không có kịch bản nào vừa để lại gạo vừa thiếu, nên cách này qua ví dụ nhưng trượt gần hết test lớn.
- Điều kiện nhảy phải là bến $\le r$ (một lần chạm đúng ở bến $r$ vẫn tính), viết nhầm $< r$ là sai.
- Tổng tiền tố tới $2 \cdot 10^{12}$ và các tổng đáp án tới $10^{18}$: phải dùng
long longở mọi chỗ.
Bộ test chấm "bắt" những lỗi nào?
Bộ test có 36 test (8 – 6 – 7 – 7 – 8 theo subtask), các test lớn có $N = 2 \cdot 10^5$ và $5 \cdot 10^4$ – $8 \cdot 10^4$ kịch bản dài hàng chục nghìn bến. Subtask 3 và 5 có $C$ nhỏ nên trung bình mỗi kịch bản chạm biên hơn $10^4$ lần (Cách 4 chắc chắn quá giờ); Subtask 4 dùng dãy "răng cưa": các đoạn tăng/giảm dài khoảng $3 \cdot 10^4$ bến, mỗi đoạn thay đổi nhỉnh hơn $C$ một chút, nên mỗi kịch bản chỉ chạm biên vài lần nhưng vẫn dài tới $10^5$ bến (mô phỏng chắc chắn quá giờ). Có cả test giá trị $10^7$ với $C = 10^{13}$ để bắt lỗi tràn số.
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Sub 5 | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – mô phỏng | 8/8 | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – ghe không đầy: min tiền tố | 8/8 | 6/6 | TLE | TLE | TLE | 25 |
| Cách 3 – r = N: lần chạm đầu + đi tới gốc | 8/8 | 6/6 | 7/7 | TLE | TLE | 45 |
| Cách 4 – nhảy từng lần chạm | 8/8 | 6/6 | 7/7 | 7/7 | TLE | 70 |
| Cách 5 – rừng + nhảy nhị phân (lời giải đầy đủ) | 8/8 | 6/6 | 7/7 | 7/7 | 8/8 | 100 |
| Sai: thiếu = max(0, cuối − x − Σa) ("hàm kẹp") | 5/8 | 6/6 | 0/7 | 0/7 | 0/8 | 21,25 |
| Sai: nhảy với điều kiện bến < r | 3/8 | 2/6 | 5/7 | 0/7 | 0/8 | 23,04 |
| Sai: tổng tiền tố kiểu int | 6/8 | 5/6 | 5/7 | 5/7 | 6/8 | 74,64 |
Để ý: ví dụ trong đề được chọn sao cho cả ba lời giải sai ở trên đều vẫn in đúng 2 và 9 — không kịch bản nào vừa để lại gạo vừa bị thiếu, và không có lần chạm nào (trừ lần đầu) rơi đúng vào bến $r$.
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài (đo thời gian CPU): lời giải chuẩn chạy tối đa khoảng 0,16 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3 giây. Lời giải chuẩn được đối chiếu với chương trình mô phỏng trên 1500 test nhỏ và 120 test vừa, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test và tốn tối đa khoảng 1,3 giây CPU ngay cả trên CPython.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét