QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382650#5069. VacationhhoppitreeWA 301ms193372kbC++149.6kb2024-04-08 17:25:282024-04-08 17:25:29

Judging History

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

  • [2024-04-08 17:25:29]
  • 评测
  • 测评结果：WA
  • 用时：301ms
  • 内存：193372kb
查看
  • [2024-04-08 17:25:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

char I[26000005], *J = I, O[8000005], *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 << 21];

    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 << 21];

    inline void build()
    {
        n = bl - 1, 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, 22000038, 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, 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) {
                    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;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 16ms
memory: 128748kb

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: 280ms
memory: 193372kb

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: 301ms
memory: 185436kb

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'
English 繁體中文 简体中文

Server Time: 2024-12-02 17:31:37 | OpenSource Project