Submission #985601

#	Time	Username	Problem	Language	Result	Execution time	Memory
985601		boris_mihov	Fish 2 (JOI22_fish2)	C++17	31 / 100	2483 ms	34140 KiB

fish2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

template <class T> void chkmax(T &a, T &b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T &b) {a = std::min(a, b);};
template <class T> void chkmax(T &a, T b) {a = std::max(a, b);};
template <class T> void chkmin(T &a, T b) {a = std::min(a, b);};

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 4e18;
const int INTINF = 1e9;

int n, q;
struct QuerySegmentTree
{
    struct Node
    {
        llong sum;
        llong minPrefix; 
        llong minSuffix; 
        int minRanges;
        int lazy;
        int cnt;

        Node()
        {
            sum = minPrefix = minSuffix = cnt = lazy = 0;
            minRanges = INTINF;
        }

        void combine(Node &left, Node &right)
        {
            sum = left.sum + right.sum;
            minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
            minSuffix = std::min(right.minSuffix, right.sum + left.minSuffix);
            minRanges = std::min(left.minRanges, right.minRanges); cnt = 0;
            if (left.minRanges == minRanges) cnt += left.cnt;
            if (right.minRanges == minRanges) cnt += right.cnt;
        }

        friend void operator += (Node &left, Node right)
        {
            chkmin(left.minPrefix, left.sum + right.minPrefix);
            left.minSuffix = std::min(right.minSuffix, right.sum + left.minSuffix);
            left.sum += right.sum;
            if (left.minRanges == right.minRanges)
            {
                left.cnt += right.cnt;
            } else if (right.minRanges < left.minRanges)
            {
                left.minRanges = right.minRanges;
                left.cnt = right.cnt;
            }
        }
    };

    Node tree[4*MAXN];
    void build(int l, int r, int node, llong a[])
    {
        if (l == r)
        {
            tree[node].sum = a[l];
            tree[node].minRanges = 0;
            tree[node].minPrefix = tree[node].minSuffix = -a[l];
            tree[node].cnt = 1;
            return;
        }

        int mid = l + r >> 1;
        build(l, mid, 2*node, a);
        build(mid + 1, r, 2*node + 1, a);
        tree[node].combine(tree[2*node], tree[2*node + 1]);
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].minRanges += tree[node].lazy;
        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void updateRanges(int l, int r, int node, int queryL, int queryR, int queryValue)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy += queryValue;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        updateRanges(l, mid, 2*node, queryL, queryR, queryValue);
        updateRanges(mid + 1, r, 2*node + 1, queryL, queryR, queryValue);
        tree[node].combine(tree[2*node], tree[2*node + 1]);
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node result;
        int mid = l + r >> 1;
        if (queryL <= mid) result += query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) result += query(mid + 1, r, 2*node + 1, queryL, queryR);
        return result;
    }

    void build(llong a[])
    {
        build(1, n, 1, a);
    }

    void updateRanges(int l, int r, int val)
    {
        updateRanges(1, n, 1, l, r, val);
    }

    Node query(int l, int r)
    {
        return query(1, n, 1, l, r);
    }
};

llong a[MAXN];
llong prefix[MAXN];
std::stack <int> st;
QuerySegmentTree tree;
void solve()
{
    tree.build(a);
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + a[i];
    }

    a[0] = a[n + 1] = INF;
    st.push(0);

    for (int i = 1 ; i <= n ; ++i)
    {
        while (a[st.top()] < a[i])
        {
            st.pop();
        }

        if (st.top() < i - 1 && prefix[i - 1] - prefix[st.top()] < a[i])
        {
            tree.updateRanges(st.top() + 1, i - 1, 1);
        }

        st.push(i);
    }

    while (st.size())
    {
        st.pop();
    }

    st.push(n + 1);
    for (int i = n ; i >= 1 ; --i)
    {
        while (a[st.top()] < a[i])
        {
            st.pop();
        }

        if (i + 1 < st.top() && prefix[st.top() - 1] - prefix[i] < a[i])
        {
            tree.updateRanges(i + 1, st.top() - 1, 1);
        }
    
        st.push(i);
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        int qType;
        std::cin >> qType;
        assert(qType == 2);

        int l, r;
        std::cin >> l >> r;
        int from, to;

        int ll = l - 1, rr = r, mid;
        while (ll < rr - 1)
        {
            mid = ll + rr >> 1;
            if (tree.query(l, mid).sum + tree.query(mid + 1, r).minPrefix < 0) ll = mid;
            else rr = mid;
        }

        from = rr;
        if (rr > l)
        {
            assert(tree.query(rr, rr).sum > tree.query(l, rr - 1).sum);
        }

        assert(tree.query(rr, r).minPrefix + tree.query(rr, rr).sum >= 0);

        ll = l; rr = r + 1;
        while (ll < rr - 1)
        {
            mid = ll + rr >> 1;
            if (tree.query(l, mid - 1).minSuffix + tree.query(mid, r).sum < 0) rr = mid;
            else ll = mid;
        }

        to = ll;
        assert(tree.query(l, ll).minSuffix + tree.query(ll, ll).sum >= 0);
        if (ll < r)
        {
            assert(tree.query(ll, ll).sum > tree.query(ll + 1, r).sum);
        }

        int res = 0;
        assert (from <= to);
        res = tree.query(from, to).cnt;
        std::cout << res << '\n';
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    std::cin >> q;
}

void fastIOI()
{   
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

fish2.cpp: In member function 'void QuerySegmentTree::build(int, int, int, llong*)':
fish2.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In member function 'void QuerySegmentTree::updateRanges(int, int, int, int, int, int)':
fish2.cpp:112:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In member function 'QuerySegmentTree::Node QuerySegmentTree::query(int, int, int, int, int)':
fish2.cpp:127:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In function 'void solve()':
fish2.cpp:213:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  213 |             mid = ll + rr >> 1;
      |                   ~~~^~~~
fish2.cpp:229:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  229 |             mid = ll + rr >> 1;
      |                   ~~~^~~~

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