oj.uz

Submission #985588

# Submission time Handle Problem Language Result Execution time Memory
985588 2024-05-18T09:18:20 Z boris_mihov Fish 2 (JOI22_fish2) C++17
8 / 100
 2136 ms 34392 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;
        //     }
        // }
    
        friend Node operator + (Node &left, Node right)
        {
            Node result;
            result.sum = left.sum + right.sum;
            result.minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
            result.minSuffix = std::min(right.minSuffix, right.sum + left.minSuffix);
            result.minRanges = std::min(left.minRanges, right.minRanges); result.cnt = 0;
            if (left.minRanges == result.minRanges) result.cnt += left.cnt;
            if (right.minRanges == result.minRanges) result.cnt += right.cnt;
            return result;
        }
    };

    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 = result + query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) result = 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 + 1, mid;
        while (ll < rr - 1)
        {
            mid = ll + rr >> 1;
            llong 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;
        if (rr > l)
        {
            assert(tree.query(rr, rr).sum > tree.query(l, rr - 1).sum);
        }

        ll = l; rr = r + 1;
        while (ll < rr - 1)
        {
            mid = ll + rr >> 1;
            llong 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;
        if (ll < r)
        {
            assert(tree.query(ll, ll).sum > tree.query(ll + 1, r).sum);
        }

        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:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In member function 'void QuerySegmentTree::updateRanges(int, int, int, int, int, int)':
fish2.cpp:122:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In member function 'QuerySegmentTree::Node QuerySegmentTree::query(int, int, int, int, int)':
fish2.cpp:137:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In function 'void solve()':
fish2.cpp:223:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  223 |             mid = ll + rr >> 1;
      |                   ~~~^~~~
fish2.cpp:239:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  239 |             mid = ll + rr >> 1;
      |                   ~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 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 16988 KB Output is correct
2 Correct 44 ms 17660 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 37 ms 17496 KB Output is correct
5 Correct 44 ms 17496 KB Output is correct
6 Correct 27 ms 17668 KB Output is correct
7 Correct 20 ms 17500 KB Output is correct
8 Correct 27 ms 17500 KB Output is correct
9 Correct 20 ms 17496 KB Output is correct
10 Correct 38 ms 17500 KB Output is correct
11 Correct 35 ms 17500 KB Output is correct
12 Correct 23 ms 17496 KB Output is correct
13 Correct 24 ms 17500 KB Output is correct
14 Correct 32 ms 17496 KB Output is correct
15 Correct 33 ms 17496 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 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 16988 KB Output is correct
2 Correct 44 ms 17660 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 37 ms 17496 KB Output is correct
5 Correct 44 ms 17496 KB Output is correct
6 Correct 27 ms 17668 KB Output is correct
7 Correct 20 ms 17500 KB Output is correct
8 Correct 27 ms 17500 KB Output is correct
9 Correct 20 ms 17496 KB Output is correct
10 Correct 38 ms 17500 KB Output is correct
11 Correct 35 ms 17500 KB Output is correct
12 Correct 23 ms 17496 KB Output is correct
13 Correct 24 ms 17500 KB Output is correct
14 Correct 32 ms 17496 KB Output is correct
15 Correct 33 ms 17496 KB Output is correct
16 Correct 3 ms 16984 KB Output is correct
17 Incorrect 2136 ms 19736 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 44 ms 17660 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 37 ms 17496 KB Output is correct
5 Correct 44 ms 17496 KB Output is correct
6 Correct 27 ms 17668 KB Output is correct
7 Correct 20 ms 17500 KB Output is correct
8 Correct 27 ms 17500 KB Output is correct
9 Correct 20 ms 17496 KB Output is correct
10 Correct 38 ms 17500 KB Output is correct
11 Correct 35 ms 17500 KB Output is correct
12 Correct 23 ms 17496 KB Output is correct
13 Correct 24 ms 17500 KB Output is correct
14 Correct 32 ms 17496 KB Output is correct
15 Correct 33 ms 17496 KB Output is correct
16 Runtime error 16 ms 34392 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 16 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -