QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#182613 | #5069. Vacation | FISHER_ | ML | 0ms | 40356kb | C++14 | 5.2kb | 2023-09-18 11:19:37 | 2023-09-18 11:19:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int maxn = 200000;
struct SEG1 {
struct item {
i64 mx, pre, suf, sum;
item(int v = 0) : sum(v) { mx = pre = suf = max(v, 0); }
item operator+(const item& b) const {
item c;
c.sum = sum + b.sum;
c.mx = max(max(mx, b.mx), suf + b.pre);
c.pre = max(pre, sum + b.pre);
c.suf = max(b.suf, b.sum + suf);
return c;
}
} t[4 * maxn + 5];
inline void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
void build(int p, int l, int r, int v[]) {
if (l == r) return t[p] = item(v[l]), void();
int mid = (l + r) / 2;
build(p << 1, l, mid, v), build(p << 1 | 1, mid + 1, r, v);
pushup(p);
}
void modify(int p, int l, int r, int x, int v) {
if (l == r) return t[p] = item(v), void();
int mid = (l + r) / 2;
if (mid >= x) modify(p << 1, l, mid, x, v);
else modify(p << 1 | 1, mid + 1, r, x, v);
pushup(p);
}
item query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[p];
int mid = (l + r) / 2; item rs;
if (mid >= x) rs = rs + query(p << 1, l, mid, x, y);
if (mid < y) rs = rs + query(p << 1 | 1, mid + 1, r, x, y);
return rs;
}
} t1;
struct SEG2 {
struct item {
i64 mx, pre, suf;
item(i64 mx = 0, i64 pre = 0, i64 suf = 0) : mx(mx), pre(pre), suf(suf) {}
item operator+(const item& b) const {
item c;
c.mx = max(max(mx, b.mx), pre + b.suf);
c.pre = max(pre, b.pre), c.suf = max(suf, b.suf);
return c;
}
};
item *t;
i64 *tg1, *tg2;
void init(int len) {
t = (item*)calloc(4 * len, sizeof(item));
tg1 = (i64*)calloc(4 * len, sizeof(i64)), tg2 = (i64*)calloc(4 * len, sizeof(i64));
}
inline void mark(int p, i64 v1, i64 v2) {
t[p].pre += v1, tg1[p] += v1;
t[p].suf += v2, tg2[p] += v2;
t[p].mx += v1 + v2;
}
inline void pushdown(int p) {
if (!tg1[p] && !tg2[p]) return;
mark(p << 1, tg1[p], tg2[p]), mark(p << 1 | 1, tg1[p], tg2[p]);
tg1[p] = tg2[p] = 0;
}
inline void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
void build(int p, int l, int r, i64 v1[], i64 v2[]) {
if (l == r) return t[p] = item(-1E18, v2[l], v1[l]), void();
int mid = (l + r) / 2;
build(p << 1, l, mid, v1, v2), build(p << 1 | 1, mid + 1, r, v1, v2);
pushup(p);
}
void modify(int p, int l, int r, int x, int y, int v1, int v2) {
if (x <= l && r <= y) return mark(p, v1, v2);
pushdown(p);
int mid = (l + r) / 2;
if (mid >= x) modify(p << 1, l, mid, x, y, v1, v2);
if (mid < y) modify(p << 1 | 1, mid + 1, r, x, y, v1, v2);
pushup(p);
}
item query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[p];
pushdown(p);
int mid = (l + r) / 2; item rs;
if (mid >= x) rs = rs + query(p << 1, l, mid, x, y);
if (mid < y) rs = rs + query(p << 1 | 1, mid + 1, r, x, y);
return rs;
}
} t2[maxn + 5];
struct SEG3 {
i64 mx[4 * maxn + 5];
inline void pushup(int p) { mx[p] = max(mx[p << 1], mx[p << 1 | 1]); }
void modify(int p, int l, int r, int x, i64 v) {
if (l == r) return mx[p] = v, void();
int mid = (l + r) / 2;
if (mid >= x) modify(p << 1, l, mid, x, v);
else modify(p << 1 | 1, mid + 1, r, x, v);
pushup(p);
}
i64 query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return mx[p];
int mid = (l + r) / 2; i64 rs = 0;
if (mid >= x) rs = max(rs, query(p << 1, l, mid, x, y));
if (mid < y) rs = max(rs, query(p << 1 | 1, mid + 1, r, x, y));
return rs;
}
} t3, t4;
int lp[maxn + 5], rp[maxn + 5];
int a[2 * maxn + 5];
i64 pre[maxn + 5], suf[maxn + 5];
int main() {
int n, m, c;
scanf("%d%d%d", &n, &m, &c);
int t = (n + c - 1) / c;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
t1.build(1, 1, n, a);
for (int i = 1; i <= t; i++) {
lp[i] = (i - 1) * c + 1, rp[i] = min(i * c, n);
t3.modify(1, 1, t, i, t1.query(1, 1, c, lp[i], rp[i]).mx);
if (i > 1) {
for (int j = 1; j <= c; j++) pre[j] = pre[j - 1] + a[j + lp[i] - 1];
for (int j = c; j >= 1; j--) suf[j] = suf[j + 1] + a[j + lp[i] - c - 1];
t2[i].init(c), t2[i].build(1, 1, c, suf, pre);
t4.modify(1, 1, t, i, t2[i].t[1].mx);
}
}
for (int i = 1; i <= m; i++) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (op == 1) {
t1.modify(1, 1, n, x, y);
int b = (x - 1) / c + 1, id = x - (b - 1) * c;
t3.modify(1, 1, t, b, t1.query(1, 1, c, lp[b], rp[b]).mx);
if (b > 1) {
t2[b].modify(1, 1, c, id, c, y - a[x], 0);
t4.modify(1, 1, t, b, t2[b].t[1].mx);
}
if (b < t) {
t2[b + 1].modify(1, 1, c, 1, id, 0, y - a[x]);
t4.modify(1, 1, t, b + 1, t2[b + 1].t[1].mx);
}
a[x] = y;
} else {
int bx = (x - 1) / c + 1, by = (y - 1) / c + 1;
int idx = x - (bx - 1) * c, idy = y - (by - 1) * c;
i64 ans = 0;
if (y - x < c) ans = t1.query(1, 1, n, x, y).mx;
else {
ans = max(t1.query(1, 1, n, x, x + c - 1).mx, t1.query(1, 1, n, y - c + 1, y).mx);
if (by - bx > 1) {
ans = max(ans, t3.query(1, 1, t, bx + 1, by - 1));
if (by - bx > 2) ans = max(ans, t4.query(1, 1, t, bx + 2, by - 1));
ans = max(ans, max(t2[bx + 1].query(1, 1, c, idx, c).mx, t2[by].query(1, 1, c, 1, idy).mx));
} else ans = max(ans, t2[by].query(1, 1, c, idx, idy).mx);
}
printf("%lld\n", ans);
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 40356kb
input:
5 6 3 0 -5 -3 8 -3 2 3 5 1 2 5 2 1 5 1 4 -3 2 3 5 2 1 5
output:
8 10 0 5
result:
ok 4 number(s): "8 10 0 5"
Test #2:
score: -100
Memory Limit Exceeded
input:
200000 500000 1 387060158 961744470 37167782 737122872 -532977662 1604246 -30977399 871848791 444997246 454204578 -813187501 -660394286 448014171 -835115276 -631880452 887715308 258530352 805589560 -414653327 -156732249 -335096199 -80266237 367896009 738406627 -903652056 446120866 415658444 -1347916...