QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#383320#5069. VacationhhoppitreeWA 239ms94108kbC++149.8kb2024-04-09 10:01:472024-04-09 10:01:47

Judging History

你现在查看的是最新测评结果

  • [2024-04-09 10:01:47]
  • 评测
  • 测评结果：WA
  • 用时：239ms
  • 内存：94108kb
查看
  • [2024-04-09 10:01:47]
  • 提交

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, int flg = 0)
{
    long long *sta = nowState;
    nowState += sz;
    if (flg) {
        fill(sta, nowState, (long long)-1e18);
    }
    return sta;
}

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 long long S[16], T = 0, y;
    do y = x / 10, S[T++] = x - y * 10; while(x = y);
    while (T) *o++ = S[--T] ^ 48;
}

int 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;
    }

    inline long long cb(dt z)
    {
        auto &[A, B, C, D] = z;
        return A;
    }

    inline long long querySum(int L, int R)
    {
        if (L > R) {
            return 0ll;
        }
        long long S = 0;
        for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
            (!(L & 1)) && (S += cb(z[L ^ 1]), 0);
            (R & 1) && (S += cb(z[R ^ 1]), 0);
        }
        return S;
    }
}

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, long long, long long> operator + (tuple<long long, long long, long long, long long, long long> x, tuple<long long, long long, long long, long long, long long> y);

struct DS
{
    int len, sz;

    typedef long long LL;
    
    LL *SuA, *SuB, *MxA, *MxB, *S;

    friend inline tuple<LL, LL, LL, LL, LL> operator + (tuple<LL, LL, LL, LL, LL> x, tuple<LL, LL, LL, LL, LL> y)
    {
        auto &[A, B, C, D, E] = x;
        auto &[F, G, H, I, J] = y;
        return {A + F, B + G, max(H, C + F), max(D, I + B), max({E + F, J + B, H + D})};
    }

    inline void Build()
    {
        int t = len, z = 1;
        while (z <= t + 1) {
            z <<= 1;
        }
        sz = z;
        SuA = myMalloc(len + sz + 1, 1);
        SuB = myMalloc(len + sz + 1, 1);
        MxA = myMalloc(len + sz + 1, 1);
        MxB = myMalloc(len + sz + 1, 1);
        S = myMalloc(len + sz + 1, 1);
        for (int i = 1; i <= len; ++i) {
            SuA[i + sz] = MxA[i + sz] = Sa[i];
            SuB[i + sz] = MxB[i + sz] = Sb[i];
        }
        for (int k = (len + sz) >> 1; k; --k) {
            SuA[k] = SuA[k << 1] + SuA[k << 1 | 1];
            SuB[k] = SuB[k << 1] + SuB[k << 1 | 1];
            MxA[k] = max(MxA[k << 1 | 1], SuA[k << 1 | 1] + MxA[k << 1]);
            MxB[k] = max(MxB[k << 1], SuB[k << 1] + MxB[k << 1 | 1]);
            S[k] = max({S[k << 1] + SuA[k << 1 | 1], S[k << 1 | 1] + SuB[k << 1], MxA[k << 1 | 1] + MxB[k << 1]});
        }
        return;
    }

    inline long long query(int L, int R)
    {
        tuple<LL, LL, LL, LL, LL> tA = {0, 0, -1e18, -1e18, -1e18}, tB = {0, 0, -1e18, -1e18, -1e18};
        for (L += sz - 1, R += sz + 1; L ^ R ^ 1; L >>= 1, R >>= 1) {
            (!(L & 1)) && (tA = tA + tuple<LL, LL, LL, LL, LL>{SuA[L ^ 1], SuB[L ^ 1], MxA[L ^ 1], MxB[L ^ 1], S[L ^ 1]}, 0);
            ((R & 1)) && (tB = tuple<LL, LL, LL, LL, LL>{SuA[R ^ 1], SuB[R ^ 1], MxA[R ^ 1], MxB[R ^ 1], S[R ^ 1]} + tB, 0);
        }
        auto [A, B, C, D, E] = tA + tB;
        return E;
    }

    inline void modifyA(int k, int y)
    {
        k += sz;
        SuA[k] += y, MxA[k] += y;
        while (k >>= 1) {
            SuA[k] = SuA[k << 1] + SuA[k << 1 | 1];
            MxA[k] = max(MxA[k << 1 | 1], SuA[k << 1 | 1] + MxA[k << 1]);
            S[k] = max({S[k << 1] + SuA[k << 1 | 1], S[k << 1 | 1] + SuB[k << 1], MxA[k << 1 | 1] + MxB[k << 1]});
        }
        return;
    }

    inline void modifyB(int k, int y)
    {
        k += sz;
        SuB[k] += y, MxB[k] += y;
        while (k >>= 1) {
            SuB[k] = SuB[k << 1] + SuB[k << 1 | 1];
            MxB[k] = max(MxB[k << 1], SuB[k << 1] + MxB[k << 1 | 1]);
            S[k] = max({S[k << 1] + SuA[k << 1 | 1], S[k << 1 | 1] + SuB[k << 1], MxA[k << 1 | 1] + MxB[k << 1]});
        }
        return;
    }

    inline void modify(int type, int x, int y)
    {
        if (!type) {
            modifyA(x, y);
        } else {
            modifyB(x, y);
        }
        return;
    }
} SEG3[N];

inline long long calc(int wh, int L = 0, int R = 0, long long V = 0)
{
    if (!L) {
        return SEG3[wh].S[1];
    }
    if (SEG1::query(L, R + C) <= V) {
        return V;
    }
    L -= (wh - 1) * C, R -= (wh - 1) * C;
    return SEG3[wh].query(L, R) + SEG1::querySum((wh - 1) * C + R + 1, wh * C + L - 1);
}

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 = 1; j <= SEG3[i].len; ++j) {
            Sa[j] = a[j + (i - 1) * C];
        }
        for (int j = 1; j <= SEG3[i].len; ++j) {
            Sb[j] = 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, res));
            } else {
                res = max({res, calc(bel, L, bel * C, res), calc(ber - 1, (ber - 2) * C + 1, R - C, res)});
            }
            print(res);
            *o++ = '\n';
        }
    }
    fwrite(O, 1, o - O, stdout);
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

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: 239ms
memory: 94108kb

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: 216ms
memory: 56764kb

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
4322308420
2770770271
4544135313
4544135313
4322308420
4386413596
4386413596
3731128239
4322308420
4100474957
4266013548
4544135313
4386413596
4094787940
4386413596
4386413596
4386413596
4322308420
4266013548
4386413596
4322308420
4544135313
4386413596
4322308420
4322308420
385...

result:

wrong answer 3rd numbers differ - expected: '4443416295', found: '4322308420'
English 繁體中文 简体中文

Server Time: 2024-12-03 19:55:24 | OpenSource Project