oj.uz

Submission #985584

# Submission time Handle Problem Language Result Execution time Memory
985584 2024-05-18T09:12:48 Z boris_mihov Fish 2 (JOI22_fish2) C++17
8 / 100
 43 ms 34140 KB 
#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 = minRanges = cnt = lazy = 0;
        }

        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].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()] < std::min(a[i], a[st.top()]))
        {
            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] < std::min(a[i], a[st.top()]))
        {
            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;
            int prefix = tree.query(l, mid).sum;
            if (mid < r) prefix += tree.query(mid + 1, r).minPrefix;
            if (prefix < 0) ll = mid;
            else rr = mid;
        }

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

        to = ll;
        from = l;
        to = r;
        int res = 0;
        if (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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 39 ms 17528 KB Output is correct
3 Correct 39 ms 17808 KB Output is correct
4 Correct 43 ms 18012 KB Output is correct
5 Correct 43 ms 18004 KB Output is correct
6 Correct 29 ms 18520 KB Output is correct
7 Correct 21 ms 17752 KB Output is correct
8 Correct 31 ms 18520 KB Output is correct
9 Correct 20 ms 17756 KB Output is correct
10 Correct 39 ms 18012 KB Output is correct
11 Correct 38 ms 17756 KB Output is correct
12 Correct 24 ms 17752 KB Output is correct
13 Correct 24 ms 17756 KB Output is correct
14 Correct 34 ms 18040 KB Output is correct
15 Correct 34 ms 18288 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 39 ms 17528 KB Output is correct
3 Correct 39 ms 17808 KB Output is correct
4 Correct 43 ms 18012 KB Output is correct
5 Correct 43 ms 18004 KB Output is correct
6 Correct 29 ms 18520 KB Output is correct
7 Correct 21 ms 17752 KB Output is correct
8 Correct 31 ms 18520 KB Output is correct
9 Correct 20 ms 17756 KB Output is correct
10 Correct 39 ms 18012 KB Output is correct
11 Correct 38 ms 17756 KB Output is correct
12 Correct 24 ms 17752 KB Output is correct
13 Correct 24 ms 17756 KB Output is correct
14 Correct 34 ms 18040 KB Output is correct
15 Correct 34 ms 18288 KB Output is correct
16 Incorrect 3 ms 16988 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 39 ms 17528 KB Output is correct
3 Correct 39 ms 17808 KB Output is correct
4 Correct 43 ms 18012 KB Output is correct
5 Correct 43 ms 18004 KB Output is correct
6 Correct 29 ms 18520 KB Output is correct
7 Correct 21 ms 17752 KB Output is correct
8 Correct 31 ms 18520 KB Output is correct
9 Correct 20 ms 17756 KB Output is correct
10 Correct 39 ms 18012 KB Output is correct
11 Correct 38 ms 17756 KB Output is correct
12 Correct 24 ms 17752 KB Output is correct
13 Correct 24 ms 17756 KB Output is correct
14 Correct 34 ms 18040 KB Output is correct
15 Correct 34 ms 18288 KB Output is correct
16 Runtime error 17 ms 34140 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -