oj.uz

Submission #985600

# Submission time Handle Problem Language Result Execution time Memory
985600 2024-05-18T09:38:57 Z boris_mihov Fish 2 (JOI22_fish2) C++17
31 / 100
 2465 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 = 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;
        //     }
        // }
    
        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);
            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].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 = 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;
            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

fish2.cpp: In member function 'void QuerySegmentTree::build(int, int, int, llong*)':
fish2.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In member function 'void QuerySegmentTree::updateRanges(int, int, int, int, int, int)':
fish2.cpp:124:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In member function 'QuerySegmentTree::Node QuerySegmentTree::query(int, int, int, int, int)':
fish2.cpp:139:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int mid = l + r >> 1;
      |                   ~~^~~
fish2.cpp: In function 'void solve()':
fish2.cpp:225:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  225 |             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 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 36 ms 17500 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 39 ms 17656 KB Output is correct
5 Correct 41 ms 17496 KB Output is correct
6 Correct 31 ms 17496 KB Output is correct
7 Correct 25 ms 17496 KB Output is correct
8 Correct 27 ms 17496 KB Output is correct
9 Correct 19 ms 17656 KB Output is correct
10 Correct 37 ms 17500 KB Output is correct
11 Correct 35 ms 17496 KB Output is correct
12 Correct 23 ms 17500 KB Output is correct
13 Correct 23 ms 17536 KB Output is correct
14 Correct 40 ms 17756 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 19 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 36 ms 17500 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 39 ms 17656 KB Output is correct
5 Correct 41 ms 17496 KB Output is correct
6 Correct 31 ms 17496 KB Output is correct
7 Correct 25 ms 17496 KB Output is correct
8 Correct 27 ms 17496 KB Output is correct
9 Correct 19 ms 17656 KB Output is correct
10 Correct 37 ms 17500 KB Output is correct
11 Correct 35 ms 17496 KB Output is correct
12 Correct 23 ms 17500 KB Output is correct
13 Correct 23 ms 17536 KB Output is correct
14 Correct 40 ms 17756 KB Output is correct
15 Correct 33 ms 17496 KB Output is correct
16 Correct 3 ms 16984 KB Output is correct
17 Correct 2287 ms 18676 KB Output is correct
18 Correct 2176 ms 20052 KB Output is correct
19 Correct 2250 ms 19768 KB Output is correct
20 Correct 2312 ms 19972 KB Output is correct
21 Correct 2338 ms 20160 KB Output is correct
22 Correct 2201 ms 20052 KB Output is correct
23 Correct 2281 ms 19728 KB Output is correct
24 Correct 2328 ms 19800 KB Output is correct
25 Correct 2323 ms 19540 KB Output is correct
26 Correct 2337 ms 19996 KB Output is correct
27 Correct 2114 ms 20764 KB Output is correct
28 Correct 2132 ms 20596 KB Output is correct
29 Correct 2107 ms 21004 KB Output is correct
30 Correct 2187 ms 19564 KB Output is correct
31 Correct 2190 ms 19572 KB Output is correct
32 Correct 2410 ms 19748 KB Output is correct
33 Correct 2288 ms 20328 KB Output is correct
34 Correct 2382 ms 19936 KB Output is correct
35 Correct 2313 ms 19416 KB Output is correct
36 Correct 2233 ms 20176 KB Output is correct
37 Correct 2241 ms 19528 KB Output is correct
38 Correct 2183 ms 19952 KB Output is correct
39 Correct 2161 ms 20300 KB Output is correct
40 Correct 2465 ms 20108 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 36 ms 17500 KB Output is correct
3 Correct 38 ms 17500 KB Output is correct
4 Correct 39 ms 17656 KB Output is correct
5 Correct 41 ms 17496 KB Output is correct
6 Correct 31 ms 17496 KB Output is correct
7 Correct 25 ms 17496 KB Output is correct
8 Correct 27 ms 17496 KB Output is correct
9 Correct 19 ms 17656 KB Output is correct
10 Correct 37 ms 17500 KB Output is correct
11 Correct 35 ms 17496 KB Output is correct
12 Correct 23 ms 17500 KB Output is correct
13 Correct 23 ms 17536 KB Output is correct
14 Correct 40 ms 17756 KB Output is correct
15 Correct 33 ms 17496 KB Output is correct
16 Runtime error 17 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 19 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -