oj.uz

Submission #985596

# Submission time Handle Problem Language Result Execution time Memory
985596 2024-05-18T09:26:11 Z boris_mihov Fish 2 (JOI22_fish2) C++17
8 / 100
 2244 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;
        //     }
        // }
    
        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()] < 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;
            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);
        }

        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;
            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;
        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

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:241:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  241 |             mid = ll + rr >> 1;
      |                   ~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 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 4 ms 16988 KB Output is correct
2 Correct 36 ms 17680 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 37 ms 17496 KB Output is correct
5 Correct 43 ms 17660 KB Output is correct
6 Correct 27 ms 17500 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 17528 KB Output is correct
10 Correct 38 ms 17576 KB Output is correct
11 Correct 36 ms 17500 KB Output is correct
12 Correct 25 ms 17500 KB Output is correct
13 Correct 24 ms 17500 KB Output is correct
14 Correct 33 ms 17688 KB Output is correct
15 Correct 37 ms 17500 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 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 4 ms 16988 KB Output is correct
2 Correct 36 ms 17680 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 37 ms 17496 KB Output is correct
5 Correct 43 ms 17660 KB Output is correct
6 Correct 27 ms 17500 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 17528 KB Output is correct
10 Correct 38 ms 17576 KB Output is correct
11 Correct 36 ms 17500 KB Output is correct
12 Correct 25 ms 17500 KB Output is correct
13 Correct 24 ms 17500 KB Output is correct
14 Correct 33 ms 17688 KB Output is correct
15 Correct 37 ms 17500 KB Output is correct
16 Correct 4 ms 17244 KB Output is correct
17 Incorrect 2244 ms 18512 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 36 ms 17680 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 37 ms 17496 KB Output is correct
5 Correct 43 ms 17660 KB Output is correct
6 Correct 27 ms 17500 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 17528 KB Output is correct
10 Correct 38 ms 17576 KB Output is correct
11 Correct 36 ms 17500 KB Output is correct
12 Correct 25 ms 17500 KB Output is correct
13 Correct 24 ms 17500 KB Output is correct
14 Correct 33 ms 17688 KB Output is correct
15 Correct 37 ms 17500 KB Output is correct
16 Runtime error 18 ms 34136 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 15 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -