Submission #548104

#	Time	Username	Problem	Language	Result	Execution time	Memory
548104		apostoldaniel854	Fish 2 (JOI22_fish2)	C++14	0 / 100	12 ms	25300 KiB

fish2

#include <bits/stdc++.h>

using namespace std;

void fastios() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}

using ll = long long;


const ll inf = (1ll << 60);
const int maxn = 1e5;

struct Stuck {
    int pos;
    ll val;
    ll sum;
    int cand;
};

struct Node {
    int sol;
    ll sum;
    vector <Stuck> pref;
    vector <Stuck> suf;
};

Node seg[1 + 4 * maxn];
int N, Q;
int A[1 + maxn];

Node join(Node lnode, Node rnode, int lb, int rb) {
    Node answer;
    int ipref = 0, isuf = 0;
    answer.sum = lnode.sum + rnode.sum;
    int cand = 0;
    ll sum = 0;
    vector <int> candleft(lnode.suf.size()), candright(rnode.pref.size());
    Stuck nowleft = lnode.suf[0], nowright = rnode.pref[0];
    while (isuf + 1 < (int)lnode.suf.size() || ipref + 1 < (int)rnode.pref.size()) {
        if (isuf + 1 < (int)lnode.suf.size() && ipref + 1 < (int)rnode.pref.size()) {
            if (lnode.suf[isuf].val <= rnode.pref[ipref].val) {
                isuf++;
                nowleft = lnode.suf[isuf];
                cand += nowleft.cand;
            }
            else {
                ipref++;
                nowright = rnode.pref[ipref];
                cand += nowright.cand;
            }
        }
        else if (isuf + 1 < (int)lnode.suf.size()) {
            isuf++;
            nowleft = lnode.suf[isuf];
            cand += nowleft.cand;
        }
        else {
            ipref++;
            nowright = rnode.pref[ipref];
            cand += nowright.cand;
        }
        sum = nowleft.sum + nowright.sum;
        if (nowleft.pos == lb - 1)
            candright[ipref] = cand;
        if (nowright.pos == rb + 1)
            candleft[isuf] = cand;
        if (sum < min(nowleft.val, nowright.val) && min(nowleft.val, nowright.val) < inf)
            cand = 0;
    }
    answer.sol = cand;
    answer.pref = lnode.pref;
    answer.pref.pop_back();
    for (int i = 0; i < (int)rnode.pref.size(); i++) {
        Stuck now = rnode.pref[i];
        if (now.val > now.sum + lnode.sum)
            answer.pref.push_back({now.pos, now.val, now.sum + lnode.sum, candright[i]});
    }
    answer.suf = rnode.suf;
    answer.suf.pop_back();
    for (int i = 0; i < (int)lnode.suf.size(); i++) {
        Stuck now = lnode.suf[i];
        if (now.val > now.sum + rnode.sum)
            answer.suf.push_back({now.pos, now.val, now.sum + rnode.sum, candleft[i]});
    }
    return answer;
}

Node createNode(int pos, int val) {
    Node answer;
    answer.sum = val;
    answer.sol = 1;
    answer.pref.push_back({pos, val, 0, 0});
    answer.pref.push_back({pos + 1, inf, val, 1});
    answer.suf.push_back({pos, val, 0, 0});
    answer.suf.push_back({pos - 1, inf, val, 1});
    return answer;
}

void build(int node, int lb, int rb) {
    if (lb == rb) {
        seg[node] = createNode(lb, A[lb]);
        return;
    }
    int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
    build(lnode, lb, mid);
    build(rnode, mid + 1, rb);
    seg[node] = join(seg[lnode], seg[rnode], lb, rb);
}

void updatePos(int node, int lb, int rb, int pos, int val) {
    if (lb == rb) {
        seg[node] = createNode(pos, val);
        return;
    }
    int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
    if (pos <= mid)
        updatePos(lnode, lb, mid, pos, val);
    else
        updatePos(rnode, mid + 1, rb, pos, val);
    seg[node] = join(seg[lnode], seg[rnode], lb, rb);
}

Node queryRange(int node, int lb, int rb, int ql, int qr) {
    if (ql <= lb && rb <= qr)
        return seg[node];
    int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
    if (qr <= mid)
        return queryRange(lnode, lb, mid, ql, qr);
    if (ql > mid)
        return queryRange(rnode, mid + 1, rb, ql, qr);
    Node L = queryRange(lnode, lb, mid, ql, mid);
    Node R = queryRange(rnode, mid + 1, rb, mid + 1, qr);
    return join(L, R, ql, qr);
}

int main() {
    fastios();
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
        cin >> A[i];
    build(1, 1, N);
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            A[pos] = val;
            updatePos(1, 1, N, pos, val);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << queryRange(1, 1, N, l, r).sol << "\n";
        }
    }
    return 0;
}

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