QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382781 | #5069. Vacation | hhoppitree | WA | 277ms | 213168kb | C++14 | 9.7kb | 2024-04-08 19:04:05 | 2024-04-08 19:04:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
char I[40000050], *J = I, O[8000050], *o = O;
inline int read()
{
unsigned int x = 0;
bool zf = 0;
while ((*J < 48 || 57 < *J) && (*J) != '-') ++J;
((*J++ == '-') ? (zf = 1) : x = *(J - 1) ^ 48);
while (47 < *J && *J < 58) x = (x << 1) + (x << 3) + (*J++ ^ 48);
return (zf ? -(int)x : x);
}
inline void print(unsigned long long x)
{
static unsigned int S[16], T = 0, y;
do y = x / 10, S[T++] = x - y * 10; while(x = y);
while (T) *o++ = S[--T] ^ 48;
}
const int N = 1e6 + 5;
int n, m, C, a[N];
namespace SEG1
{
typedef long long LL;
typedef tuple<LL, LL, LL, LL> dt;
int sz;
dt z[1 << 22];
inline dt operator + (dt x, dt y)
{
auto [a, b, c, d] = x;
auto [e, f, g, h] = y;
return {a + e, max({b, f, d + g}), max(c, a + g), max(h, e + d)};
}
inline void build()
{
sz = 1;
while (sz <= n + 1) {
sz <<= 1;
}
for (int i = 1; i <= n; ++i) {
z[i + sz] = {a[i], max(a[i], 0), max(a[i], 0), max(a[i], 0)};
}
for (int i = (n + sz) >> 1; i; --i) {
z[i] = z[i << 1] + z[i << 1 | 1];
}
return;
}
inline void modify(int x)
{
z[x + sz] = {a[x], max(a[x], 0), max(a[x], 0), max(a[x], 0)};
x += sz;
while (x >>= 1) {
z[x] = z[x << 1] + z[x << 1 | 1];
}
return;
}
inline long long query(int L, int R)
{
dt rL = {0, 0, 0, 0}, rR = {0, 0, 0, 0};
for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
(!(L & 1)) && (rL = rL + z[L ^ 1], 0);
(R & 1) && (rR = z[R ^ 1] + rR, 0);
}
auto [A, B, C, D] = rL + rR;
return B;
}
}
int bl;
long long glo1[N], glo2[N];
namespace SEG2
{
int n, sz;
long long mx[1 << 22];
inline void build()
{
n = bl - 2, sz = 1;
while (sz <= n + 1) {
sz <<= 1;
}
for (int i = 1; i <= n; ++i) {
mx[i + sz] = max(glo1[i], glo2[i]);
}
for (int i = (n + sz) >> 1; i; --i) {
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
return;
}
inline void modify(int x)
{
mx[x + sz] = max(glo1[x], glo2[x]);
x += sz;
while (x >>= 1) {
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
return;
}
inline long long query(int L, int R)
{
long long res = 0;
for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
(!(L & 1)) && (res = max(res, mx[L ^ 1]));
((R & 1)) && (res = max(res, mx[R ^ 1]));
}
return res;
}
}
long long Sa[N], Sb[N];
inline tuple<long long, long long, long long> operator + (tuple<long long, long long, long long> x, tuple<long long, long long, long long> y);
struct DS
{
int len;
typedef long long LL;
vector<LL> MxA, MxB, LazyA, LazyB, S;
friend inline tuple<LL, LL, LL> operator + (tuple<LL, LL, LL> x, tuple<LL, LL, LL> y)
{
long long A, B, C, D, E, F;
tie(A, B, C) = x, tie(D, E, F) = y;
return {max(A, D), max(B, E), max({C, F, B + D})};
}
void build(int k, int l, int r)
{
if (l == r) {
MxA[k] = Sa[l];
MxB[k] = Sb[l];
S[k] = -1e18;
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
tie(MxA[k], MxB[k], S[k]) = tuple<LL, LL, LL>(MxA[k << 1], MxB[k << 1], S[k << 1]) +
tuple<LL, LL, LL>(MxA[k << 1 | 1], MxB[k << 1 | 1], S[k << 1 | 1]);
return;
}
inline void Build()
{
int t = 2 * len, z = 1;
while (z < t) {
z <<= 1;
}
MxA.resize(z + 1), MxB.resize(z + 1);
LazyA.resize(z + 1), LazyB.resize(z + 1);
S.resize(z + 1);
build(1, 1, len);
return;
}
tuple<LL, LL, LL> query(int k, int l, int r, int x, int y)
{
if (l >= x && r <= y) {
return {MxA[k], MxB[k], S[k]};
}
pushdown(k);
int mid = (l + r) >> 1;
if (mid >= y) {
return query(k << 1, l, mid, x, y);
}
if (mid < x) {
return query(k << 1 | 1, mid + 1, r, x, y);
}
return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
}
inline void addTagA(int k, int x)
{
LazyA[k] += x;
MxA[k] += x;
S[k] += x;
return;
}
inline void addTagB(int k, int x)
{
LazyB[k] += x;
MxB[k] += x;
S[k] += x;
return;
}
inline void pushdown(int k)
{
if (LazyA[k]) {
addTagA(k << 1, LazyA[k]);
addTagA(k << 1 | 1, LazyA[k]);
LazyA[k] = 0;
}
if (LazyB[k]) {
addTagB(k << 1, LazyB[k]);
addTagB(k << 1 | 1, LazyB[k]);
LazyB[k] = 0;
}
return;
}
void modifyA(int k, int l, int r, int x, int y)
{
if (r <= x) {
addTagA(k, y);
return;
}
if (l > x) {
return;
}
pushdown(k);
int mid = (l + r) >> 1;
modifyA(k << 1, l, mid, x, y);
modifyA(k << 1 | 1, mid + 1, r, x, y);
tie(MxA[k], MxB[k], S[k]) = tuple<LL, LL, LL>(MxA[k << 1], MxB[k << 1], S[k << 1]) +
tuple<LL, LL, LL>(MxA[k << 1 | 1], MxB[k << 1 | 1], S[k << 1 | 1]);
return;
}
void modifyB(int k, int l, int r, int x, int y)
{
if (l >= x) {
addTagB(k, y);
return;
}
if (r < x) {
return;
}
pushdown(k);
int mid = (l + r) >> 1;
modifyB(k << 1, l, mid, x, y);
modifyB(k << 1 | 1, mid + 1, r, x, y);
tie(MxA[k], MxB[k], S[k]) = tuple<LL, LL, LL>(MxA[k << 1], MxB[k << 1], S[k << 1]) +
tuple<LL, LL, LL>(MxA[k << 1 | 1], MxB[k << 1 | 1], S[k << 1 | 1]);
return;
}
inline void modify(int type, int x, int y)
{
if (!type) {
modifyA(1, 1, len, x, y);
} else {
modifyB(1, 1, len, x, y);
}
return;
}
} SEG3[N];
inline long long calc(int wh, int L = 0, int R = 0)
{
if (!L) {
L = 1, R = min((wh + 1) * C, n) - wh * C;
} else {
L -= (wh - 1) * C, R -= (wh - 1) * C;
}
long long A, B, C;
tie(A, B, C) = SEG3[wh].query(1, 1, SEG3[wh].len, L, R);
return C;
}
signed main()
{
fread(I, 1, 40000038, stdin);
n = read(), m = read(), C = read();
bl = (n - 1) / C + 1;
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
n += C - (n % C);
SEG1::build();
for (int i = 2; i <= bl - 1; ++i) {
long long s = 0, mx = 0;
for (int j = (i - 1) * C + 1; j <= i * C && j <= n; ++j) {
mx = max(mx, s = max(s, 0ll) + a[j]);
}
glo1[i] = mx;
}
for (int i = 1; i <= bl - 1; ++i) {
SEG3[i].len = min((i + 1) * C, n) - i * C;
for (int j = C; j; --j) {
Sa[j] = Sa[j + 1] + a[j + (i - 1) * C];
}
for (int j = 1; j <= SEG3[i].len; ++j) {
Sb[j] = Sb[j - 1] + a[j + i * C];
}
SEG3[i].Build();
}
for (int i = 2; i <= bl - 2; ++i) {
glo2[i] = calc(i);
}
SEG2::build();
while (m--) {
int opt = read(), L = read(), R = read();
if (opt == 1) {
if (a[L] == R) {
continue;
}
int D = R - a[L];
a[L] = R;
SEG1::modify(L);
int bel = (L - 1) / C + 1, flg = max(glo1[bel], glo2[bel]);
if (bel >= 2 && bel <= bl - 1) {
glo1[bel] = SEG1::query((bel - 1) * C + 1, bel * C);
}
if (bel >= 2) {
SEG3[bel - 1].modify(1, L - (bel - 1) * C, D);
}
if (bel <= bl - 1) {
SEG3[bel].modify(0, L - (bel - 1) * C, D);
}
if (bel >= 3) {
int tv = max(glo1[bel - 1], glo2[bel - 1]);
glo2[bel - 1] = calc(bel - 1);
if (max(glo1[bel - 1], glo2[bel - 1]) != tv && bel <= bl - 1) {
SEG2::modify(bel - 1);
}
}
if (bel >= 2 && bel <= bl - 2) {
glo2[bel] = calc(bel);
}
if (bel >= 2 && bel <= bl - 2 && flg != max(glo1[bel], glo2[bel])) {
SEG2::modify(bel);
}
} else {
if (R - L + 1 <= C) {
print(SEG1::query(L, R));
*o++ = '\n';
continue;
}
int bel = (L - 1) / C + 1, ber = (R - 1) / C + 1;
long long res = (bel + 2 >= ber ? 0ll : SEG2::query(bel + 1, ber - 2));
if (bel + 1 != ber) {
res = max(res, glo1[ber - 1]);
}
res = max({res, SEG1::query(L, L + C - 1), SEG1::query(R - C + 1, R)});
if (ber == bel + 1) {
res = max(res, calc(bel, L, R - C));
} else {
res = max({res, calc(bel, L, bel * C), calc(ber - 1, (ber - 2) * C + 1, R - C)});
}
print(res);
*o++ = '\n';
}
}
fwrite(O, 1, o - O, stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 140088kb
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: 0
Accepted
time: 277ms
memory: 213168kb
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...
output:
999902477 999981999 999343404 999847372 999957587 998160312 999981999 999981999 999981999 999980061 999981999 999981999 999981999 999876122 999981999 999996602 999981999 999981999 999981999 999723649 999981999 999957587 999896087 999981999 999981999 999981999 999981999 999981999 999957587 999981999 ...
result:
ok 250051 numbers
Test #3:
score: -100
Wrong Answer
time: 229ms
memory: 201664kb
input:
200000 500000 5 802774074 383481934 -295470374 285359286 751657057 197444479 626916547 -828168464 288373833 -493446966 -208422769 956745384 919286225 959643271 -176531848 -380256966 357111771 -50890039 -637284768 -337010918 259019684 752475630 -259898780 98620995 -704832505 -532710796 -971600790 -84...
output:
4544135313 4544135313 4443416295 3390067591 4544135313 4544135313 4322308420 4386413596 4386413596 4165697630 4322308420 4287938127 4443416295 4544135313 4386413596 4165697630 4386413596 4386413596 4386413596 4323325838 4443416295 4386413596 4385851999 4544135313 4443416295 4443416295 4323325838 432...
result:
wrong answer 12040th numbers differ - expected: '4323325838', found: '5044550592'