oj.uz

Submission #985601

# Submission time Handle Problem Language Result Execution time Memory
985601 2024-05-18T09:40:49 Z boris_mihov Fish 2 (JOI22_fish2) C++17
31 / 100
 2483 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;
            }
        }
    };

    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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 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 37 ms 17676 KB Output is correct
3 Correct 37 ms 17500 KB Output is correct
4 Correct 36 ms 17520 KB Output is correct
5 Correct 38 ms 17500 KB Output is correct
6 Correct 26 ms 17500 KB Output is correct
7 Correct 19 ms 17500 KB Output is correct
8 Correct 31 ms 17532 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 29 ms 17756 KB Output is correct
13 Correct 23 ms 17496 KB Output is correct
14 Correct 32 ms 17500 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 20 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 16988 KB Output is correct
2 Correct 37 ms 17676 KB Output is correct
3 Correct 37 ms 17500 KB Output is correct
4 Correct 36 ms 17520 KB Output is correct
5 Correct 38 ms 17500 KB Output is correct
6 Correct 26 ms 17500 KB Output is correct
7 Correct 19 ms 17500 KB Output is correct
8 Correct 31 ms 17532 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 29 ms 17756 KB Output is correct
13 Correct 23 ms 17496 KB Output is correct
14 Correct 32 ms 17500 KB Output is correct
15 Correct 33 ms 17496 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 2204 ms 18068 KB Output is correct
18 Correct 2173 ms 18592 KB Output is correct
19 Correct 2184 ms 18428 KB Output is correct
20 Correct 2245 ms 18024 KB Output is correct
21 Correct 2243 ms 18332 KB Output is correct
22 Correct 2239 ms 18008 KB Output is correct
23 Correct 2198 ms 18144 KB Output is correct
24 Correct 2251 ms 18156 KB Output is correct
25 Correct 2253 ms 18080 KB Output is correct
26 Correct 2249 ms 18420 KB Output is correct
27 Correct 2082 ms 18192 KB Output is correct
28 Correct 2107 ms 18220 KB Output is correct
29 Correct 2138 ms 18628 KB Output is correct
30 Correct 2201 ms 17996 KB Output is correct
31 Correct 2239 ms 17680 KB Output is correct
32 Correct 2296 ms 17920 KB Output is correct
33 Correct 2169 ms 18196 KB Output is correct
34 Correct 2284 ms 17924 KB Output is correct
35 Correct 2236 ms 18212 KB Output is correct
36 Correct 2205 ms 18456 KB Output is correct
37 Correct 2236 ms 18004 KB Output is correct
38 Correct 2238 ms 17744 KB Output is correct
39 Correct 2147 ms 18504 KB Output is correct
40 Correct 2483 ms 18480 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 37 ms 17676 KB Output is correct
3 Correct 37 ms 17500 KB Output is correct
4 Correct 36 ms 17520 KB Output is correct
5 Correct 38 ms 17500 KB Output is correct
6 Correct 26 ms 17500 KB Output is correct
7 Correct 19 ms 17500 KB Output is correct
8 Correct 31 ms 17532 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 29 ms 17756 KB Output is correct
13 Correct 23 ms 17496 KB Output is correct
14 Correct 32 ms 17500 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 20 ms 34140 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -