QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#383090 | #5069. Vacation | hhoppitree | WA | 514ms | 90216kb | C++14 | 9.9kb | 2024-04-08 21:43:14 | 2024-04-08 21:43:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long States[N * 20], *nowState = States;
inline long long* myMalloc(int sz)
{
long long *sta = nowState;
nowState += sz;
return sta;
}
char I[40000050], *J = I, O[8000050], *o = O;
inline long long read()
{
unsigned long long 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 ? -(long long)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;
}
long long n, m, C;
long long 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], 0ll), max(a[i], 0ll), max(a[i], 0ll)};
}
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], 0ll), max(a[x], 0ll), max(a[x], 0ll)};
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;
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 = myMalloc(z + 1);
MxB = myMalloc(z + 1);
LazyA = myMalloc(z + 1);
LazyB = myMalloc(z + 1);
S = myMalloc(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, long long x)
{
LazyA[k] += x;
MxA[k] += x;
S[k] += x;
return;
}
inline void addTagB(int k, long long 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) {
return SEG3[wh].S[1];
}
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();
}
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;
long long 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) {
long long 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: 0ms
memory: 15992kb
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: 242ms
memory: 90216kb
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: 0
Accepted
time: 300ms
memory: 80976kb
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:
ok 249998 numbers
Test #4:
score: 0
Accepted
time: 342ms
memory: 78208kb
input:
200000 500000 10 294669347 -694582751 -596596961 -126098203 564639690 -654836388 -393227122 -835904658 699214733 147549986 -60745155 364274902 6365735 182107449 544381751 8255910 -581710335 -254751705 -547803021 113792037 -526424167 -948294769 -456727013 -172857504 627985189 -660230969 -233539222 -3...
output:
6382761194 6975829216 5771846079 7795537121 6975829216 7251135307 7795537121 7795537121 7795537121 7251135307 6382761194 7251135307 7795537121 7795537121 7251135307 6166320975 7251135307 5845186875 6304374419 7795537121 6533205084 6975829216 7795537121 6051983693 7795537121 6533205084 6671392380 553...
result:
ok 249912 numbers
Test #5:
score: 0
Accepted
time: 402ms
memory: 69296kb
input:
200000 500000 50 682924062 -410171362 727046928 -248951706 447030590 -828489266 -766563199 -502548010 -959695696 -583569857 -305162329 -550851997 -462615752 -822803313 -640012170 267251148 340565257 -111341766 689672874 -515868601 -242875719 -162422332 49211711 277849676 -108078900 -304560362 -50058...
output:
15856525974 15423765469 15423765469 15728637453 15856525974 15728637453 15728637453 15060577990 15856525974 15856525974 15060577990 15856525974 15856525974 15856525974 15060577990 15728637453 15856525974 15856525974 15856525974 15856525974 15592293852 15856525974 15592293852 15856525974 15423765469 ...
result:
ok 249945 numbers
Test #6:
score: 0
Accepted
time: 463ms
memory: 73348kb
input:
200000 500000 100 -861625642 488714758 151701153 337144530 -318293290 -765334091 -210261967 -253541961 993816332 -736017816 52189861 -428475798 -281280689 875335671 889366119 -863352867 4083578 382040499 152212580 696548442 348806166 -403452187 -91390158 -86542614 -915521115 -615218473 374313280 -60...
output:
22356669163 16483275109 20675548507 20675548507 18341749229 16758974141 19886103941 22356669163 12776363397 19919404941 22356669163 22356669163 22356669163 20675548507 22356669163 22356669163 20675548507 22356669163 19886103941 20352085144 22356669163 22356669163 19064838381 19782436621 20675548507 ...
result:
ok 250001 numbers
Test #7:
score: -100
Wrong Answer
time: 514ms
memory: 65168kb
input:
200000 500000 500 560111824 156076602 -300062433 -135130960 172514238 -107440145 332810571 -462042876 -248802506 163714210 -330670470 42796256 -486522143 -669315725 -916663241 992138762 904514188 -430525531 509990997 -414368382 886580739 968753025 -783053293 60399434 -189320070 -2477706 -334706343 4...
output:
8537564439 38429372430 32781696692 35966554114 8537564439 8537564439 6169982499 40039498632 6169982499 42076835781 8537564439 42076835781 40039498632 8537564439 40039498632 8537564439 272958403 40936887546 38671383728 35611226388 42076835781 8537564439 8537564439 8537564439 35611226388 42076835781 2...
result:
wrong answer 1st numbers differ - expected: '51487237399', found: '8537564439'