제출 #1254981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254981		MisterReaper	Fish 2 (JOI22_fish2)	C++20	100 / 100	1908 ms	74464 KiB

fish2

// File B.cpp created on 08.08.2025 at 11:52:11
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1E5) + 5;

int N;
int A[max_N];

struct Info {
    int l, r;
    std::vector<int> pntl;
    std::vector<int> frql;
    std::vector<i64> suml;

    std::vector<int> pntr;
    std::vector<int> frqr;
    std::vector<i64> sumr;
    Info() {}
    Info(int x) {
        l = r = x;
        pntl = {x};
        frql = {1};
        suml = {A[x]};

        pntr = {x};
        frqr = {1};
        sumr = {A[x]};
    }
} tree[max_N << 1];

void clear(std::vector<int>& pnt, std::vector<int>& frq, std::vector<i64>& sum) {
    std::vector<int> npnt;
    std::vector<int> nfrq;
    std::vector<i64> nsum;
    for (int i = 0; i < int(pnt.size()); ++i) {
        if (frq[i]) {
            npnt.emplace_back(pnt[i]);
            nfrq.emplace_back(frq[i]);
            nsum.emplace_back(sum[i]);
        }
    }
    pnt = std::move(npnt);
    frq = std::move(nfrq);
    sum = std::move(nsum);
}

Info operator+ (const Info& lhs, const Info& rhs) {
    Info res;
    res.l = lhs.l;
    res.r = rhs.r;
    {
        int sizl = int(lhs.pntl.size());
        int sizr = int(rhs.pntl.size());
        int n = sizl + sizr;
        res.pntl.insert(res.pntl.end(), lhs.pntl.begin(), lhs.pntl.end());
        res.pntl.insert(res.pntl.end(), rhs.pntl.begin(), rhs.pntl.end());
        res.frql.resize(n);
        res.suml.resize(n);
        for (int i = 0; i < n; ++i) {
            if (i < sizl) {
                res.suml[i] = lhs.suml[i];
            } else {
                res.suml[i] = lhs.suml.back() + rhs.suml[i - sizl];
            }
        }

        { // Case 1: sol childimin sola yapisik ama saga yapisik olmayani ekle
            for (int i = 0; i < sizl - 1; ++i) {
                res.frql[i] += lhs.frql[i];
            }
        }
        { // Case 2: sol childimin saga yapisik olanlari sola ve saga buyutup ekle
            int m = int(lhs.pntr.size());
            int l = m, r = -1;
            for (int i = m - 1; i >= 0; --i) {
                l = std::min(l, i);
                while (true) {
                    i64 sum = lhs.sumr[l] + (r == -1 ? 0 : rhs.suml[r]);
                    if (r != sizr - 1 && sum >= A[r == -1 ? rhs.l : (rhs.pntl[r] + 1)]) {
                        r++;
                        continue;
                    }
                    if (l != 0 && sum >= A[lhs.pntr[l] - 1]) {
                        l--;
                        continue;
                    }
                    break;
                }
                if (l == 0) {
                    res.frql[sizl + r] += lhs.frqr[i];
                }
            }
        }
        { // Case 3: sag childimin sola yapisik kaplayanlari buyutup eger sola yapisirlarsa ekle
            int m = int(lhs.pntr.size());
            int l = m, r = -1;
            for (int i = 0; i < sizr; ++i) {
                r = std::max(r, i);
                while (true) {
                    i64 sum = (l == m ? 0 : lhs.sumr[l]) + rhs.suml[r];
                    if (r != sizr - 1 && A[rhs.pntl[r] + 1] <= sum) {
                        r++;
                        continue;
                    }
                    if (l != 0 && A[l == m ? lhs.r : (lhs.pntr[l] - 1)] <= sum) {
                        l--;
                        continue;
                    }
                    break;
                }
                if (l == 0) {
                    res.frql[sizl + r] += rhs.frql[i];
                }
            }
        }
    }

    {
        int sizl = int(lhs.pntr.size());
        int sizr = int(rhs.pntr.size());
        int n = sizl + sizr;
        res.pntr.insert(res.pntr.end(), lhs.pntr.begin(), lhs.pntr.end());
        res.pntr.insert(res.pntr.end(), rhs.pntr.begin(), rhs.pntr.end());
        res.frqr.resize(n);
        res.sumr.resize(n);
        for (int i = 0; i < n; ++i) {
            if (i < sizl) {
                res.sumr[i] = lhs.sumr[i] + rhs.sumr[0];
            } else {
                res.sumr[i] = rhs.sumr[i - sizl];
            }
        }

        { // Case 1: sag childimin saga yapisik ama sola yapisik olmayani ekle
            for (int i = 1; i < sizr; ++i) {
                res.frqr[sizl + i] += rhs.frqr[i];
            }
        }
        { // Case 2: sag childimin sola yapisik olanlari sola ve saga buyutup ekle
            int m = int(rhs.pntl.size());
            int l = sizl, r = -1;
            for (int i = 0; i < m; ++i) {
                r = std::max(r, i);
                while (true) {
                    i64 sum = (l == sizl ? 0 : lhs.sumr[l]) + rhs.suml[r];
                    if (r != m - 1 && sum >= A[rhs.pntl[r] + 1]) {
                        r++;
                        continue;
                    }
                    if (l != 0 && sum >= A[l == sizl ? lhs.r : (lhs.pntr[l] - 1)]) {
                        l--;
                        continue;
                    }
                    break;
                }
                if (r == m - 1) {
                    res.frqr[l] += rhs.frql[i];
                }
            }
        }
        { // Case 3: sol childimin saga yapisik kaplayanlari buyutup eger saga yapisirlarsa ekle
            int m = int(rhs.pntl.size());
            int l = sizl, r = -1;
            for (int i = sizl - 1; i >= 0; --i) {
                l = std::min(l, i);
                while (true) {
                    i64 sum = lhs.sumr[l] + (r == -1 ? 0 : rhs.suml[r]);
                    if (r != m - 1 && sum >= A[r == -1 ? rhs.l : (rhs.pntl[r] + 1)]) {
                        r++;
                        continue;
                    }
                    if (l != 0 && sum >= A[lhs.pntr[l] - 1]) {
                        l--;
                        continue;
                    }
                    break;
                }
                if (r == m - 1) {
                    res.frqr[l] += lhs.frqr[i];
                }
            }
        }
    }

    clear(res.pntl, res.frql, res.suml);
    clear(res.pntr, res.frqr, res.sumr);

    return res;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)

void build(int v, int l, int r) {
    if (l == r) {
        tree[v] = {l};
        return;
    }
    def;
    build(lv, l, mid);
    build(rv, mid + 1, r);
    tree[v] = tree[lv] + tree[rv];
    debug(l, r);
    debug(tree[v].l, tree[v].r);
    debug(tree[v].pntl);
    debug(tree[v].frql);
    debug(tree[v].suml);
    debug(tree[v].pntr);
    debug(tree[v].frqr);
    debug(tree[v].sumr);
    // if (l == 0 && r == 4) exit(0);
}

void modify(int v, int l, int r, int p, int x) {
    if (l == r) {
        A[p] = x;
        tree[v] = {p};
        return;
    }
    def;
    if (p <= mid) {
        modify(lv, l, mid, p, x);
    } else {
        modify(rv, mid + 1, r, p, x);
    }
    tree[v] = tree[lv] + tree[rv];
}

Info get(int v, int l, int r, int ql, int qr) {
    if (ql == l && r == qr) {
        return tree[v];
    }
    def;
    if (qr <= mid) {
        return get(lv, l, mid, ql, qr);
    } else if (mid + 1 <= ql) {
        return get(rv, mid + 1, r, ql, qr); 
    } else {
        return get(lv, l, mid, ql, mid)
             + get(rv, mid + 1, r, mid + 1, qr);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    build(0, 0, N - 1);
    // exit(0);

    int Q;
    std::cin >> Q;

    for (int _ = 0; _ < Q; ++_) {
        int TP;
        std::cin >> TP;
        if (TP == 1) {
            int P, X;
            std::cin >> P >> X;
            --P;
            modify(0, 0, N - 1, P, X);
        } else {
            int L, R;
            std::cin >> L >> R;
            --L, --R;
            auto nd = get(0, 0, N - 1, L, R);
            std::cout << nd.frql.back() << '\n';
        }
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17