QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383261#5069. VacationhhoppitreeWA 1ms3688kbC++149.6kb2024-04-09 08:20:162024-04-09 08:20:16

Judging History

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

  • [2024-04-09 08:20:16]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3688kb
查看
  • [2024-04-09 08:20:16]
  • 提交

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

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;

    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)
    {
        long long A, B, C, D, E, F, G, H, I, J;
        tie(A, B, C, D, E) = x, tie(F, G, H, I, J) = y;
        return {A + F, B + G, max(H, C + F), max(D, I + B), max({E, J, H + D})};
    }

    void build(int k, int l, int r)
    {
        if (l == r) {
            SuA[k] = Sa[l];
            SuB[k] = Sb[l];
            MxA[k] = max(Sa[l], 0ll);
            MxB[k] = max(Sb[l], 0ll);
            S[k] = -1e18;
            return;
        }
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        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], S[k << 1 | 1], MxA[k << 1 | 1] + MxB[k << 1]});
        return;
    }

    inline void Build()
    {
        int t = 2 * len, z = 1;
        while (z < t) {
            z <<= 1;
        }
        SuA = myMalloc(z + 1);
        SuB = myMalloc(z + 1);
        MxA = myMalloc(z + 1);
        MxB = myMalloc(z + 1);
        S = myMalloc(z + 1);
        build(1, 1, len);
        return;
    }

    tuple<LL, LL, LL, LL, LL> query(int k, int l, int r, int x, int y)
    {
        if (l >= x && r <= y) {
            return {SuA[k], SuB[k], MxA[k], MxB[k], S[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);
    }

    void modifyA(int k, int l, int r, int x, int y)
    {
        if (l == r) {
            SuA[k] += y;
            MxA[k] += y;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modifyA(k << 1, l, mid, x, y);
        } else {
            modifyA(k << 1 | 1, mid + 1, r, x, y);
        }
        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], S[k << 1 | 1], MxA[k << 1 | 1] + MxB[k << 1]});
        return;
    }

    void modifyB(int k, int l, int r, int x, int y)
    {
        if (l == r) {
            SuB[k] += y;
            MxB[k] += y;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modifyB(k << 1, l, mid, x, y);
        } else {
            modifyB(k << 1 | 1, mid + 1, r, x, y);
        }
        SuB[k] = SuB[k << 1] + SuB[k << 1 | 1];
        MxB[k] = max(MxB[k << 1], SuB[k << 1] + MxB[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, 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;
    long long A, B, C, D, E;
    tie(A, B, C, D, E) = SEG3[wh].query(1, 1, SEG3[wh].len, L, R);
    return E;
}

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 = SEG3[i].len; j; --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;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3688kb

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
18
0
5

result:

wrong answer 2nd numbers differ - expected: '10', found: '18'
English 繁體中文 简体中文

伺服器時間: 2024-12-12 00:21:05 | 開源專案