oj.uz

Submission #876319

# Submission time Handle Problem Language Result Execution time Memory
876319 2023-11-21T14:34:14 Z danikoynov Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 14600 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;


int n, q;
ll a[maxn], pref[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    cin >> q;
    a[0] = 1e9 + 10;
    a[n + 1] = 1e9 + 10;

}

vector < pair < int, int > > ranges;
void get_ranges()
{

    for (int i = 1; i <= n; i ++)
        pref[i] = pref[i - 1] + a[i];
    pref[n + 1] = pref[n];

    ranges.clear();
    stack < int > st;
    st.push(0);
    for (int i = 1; i <= n; i ++)
    {
        while(!st.empty() && a[st.top()] < a[i])
            st.pop();


        if (pref[i - 1] - pref[st.top()] < a[i])
            ranges.push_back({st.top() + 1, i - 1});

        st.push(i);
    }

    while(!st.empty())
        st.pop();
    st.push(n + 1);
    for (int i = n; i > 0; i --)
    {
        while(!st.empty() && a[st.top()] < a[i])
            st.pop();

        if (pref[st.top() - 1] - pref[i] < a[i])
            ranges.push_back({i + 1, st.top() - 1});

        st.push(i);
    }
}

int b[maxn];

struct node
{
    int cnt, mx;

    node(int _cnt = 0, int _mx = 1e9 + 10)
    {
        cnt = _cnt;
        mx = _mx;
    }
};

node tree[4 * maxn];

node merge_node(node lf, node rf)
{
    if (lf.cnt == -1 || rf.mx < lf.mx)
        return rf;
    if (rf.cnt == -1 || lf.mx < rf.mx)
        return lf;

    return node(lf.cnt + rf.cnt, lf.mx);
}

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].mx = b[left];
        tree[root].cnt = 1;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return node(-1, 1e9 + 10);

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;

    return merge_node(query(root * 2, left, mid, qleft, qright),
            query(root * 2 + 1, mid + 1, right, qleft, qright));
}

ll values[maxn];

struct segment_tree
{
    ll tree[4 * maxn], lazy[4 * maxn];


    void build_tree(int root, int left, int right)
    {
        lazy[root] = 0;
        if (left == right)
        {
            tree[root] = values[left];
            return;
        }

        int mid = (left + right) / 2;
        build_tree(root * 2, left, mid);
        build_tree(root * 2 + 1, mid + 1, right);

        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }

    void push_lazy(int root, int left, int right)
    {
        tree[root] += lazy[root];
        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }

        lazy[root] = 0;
    }

    void update_range(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] += val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

        tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
    }

    ll walk_left(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft || tree[root] < val)
            return n + 1;

        if (left == right)
            return left;

        int mid = (left + right) / 2;
        if (left >= qleft && right <= qright)
        {
            if (tree[root * 2] > val)
                return walk_left(root * 2, left, mid, qleft, qright, val);
            return walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val);
        }

        return min(walk_left(root * 2, left, mid, qleft, qright, val),
                walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val));
    }

    ll walk_right(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft || tree[root] < val)
            return n + 1;

        if (left == right)
            return left;

        int mid = (left + right) / 2;
        if (left >= qleft && right <= qright)
        {
            if (tree[root * 2 + 1] > val)
                    return walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val);
            return walk_right(root * 2, left, mid, qleft, qright, val);
        }

        return min(walk_right(root * 2, left, mid, qleft, qright, val),
                walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val));
    }
};

segment_tree left_tree;

void solve_query(int left, int right)
{

    //for (pair < int, int > cur : ranges)
      //  cout << cur.first << " : " << cur.second << endl;


    int lb = left, rb = right;
    for (int i = left; i <= right; i ++)
    {
        //if (a[i] > pref[i - 1] - pref[left - 1])
          //  lb = max(lb, i);
        if (a[i] > pref[right] - pref[i])
            rb = min(rb, i);
    }
    lb = left_tree.walk_right(1, 1, n, left, right, - pref[left - 1]);


    /**int minx = 1e9;
    for (int i = lb; i <= rb; i ++)
        minx = min(minx, b[i]);

    int ans = 0;
    for (int i = lb; i <= rb; i ++)
        if (b[i] == minx)
        ans ++;*/

    cout << query(1, 1, n, lb, rb).cnt << endl;
}

void restructure()
{
    get_ranges();
    for (int i = 1; i <= n; i ++)
        b[i] = 0;
    for (pair < int, int > cur : ranges)
        for (int i = cur.first; i <= cur.second; i ++)
        b[i] ++;
    build_tree(1, 1, n);
    for (int i = 1; i <= n; i ++)
    {
        values[i] = a[i] - pref[i - 1];
    }
    left_tree.build_tree(1, 1, n);
}
void simulate()
{
    restructure();
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int idx;
            ll x;
            cin >> idx >> x;
            a[idx] = x;
            restructure();
        }
        else
        {
            int l, r;
            cin >> l >> r;
            solve_query(l, r);
        }
    }
}
void solve()
{
    input();
    simulate();
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Incorrect 1 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 13 ms 14136 KB Output is correct
3 Correct 13 ms 14036 KB Output is correct
4 Correct 13 ms 14096 KB Output is correct
5 Correct 13 ms 14036 KB Output is correct
6 Correct 15 ms 13780 KB Output is correct
7 Correct 13 ms 14152 KB Output is correct
8 Correct 16 ms 13776 KB Output is correct
9 Correct 12 ms 13780 KB Output is correct
10 Correct 13 ms 14036 KB Output is correct
11 Correct 12 ms 14600 KB Output is correct
12 Correct 12 ms 13780 KB Output is correct
13 Correct 14 ms 13776 KB Output is correct
14 Correct 13 ms 14036 KB Output is correct
15 Correct 14 ms 14040 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Incorrect 1 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 13 ms 14136 KB Output is correct
3 Correct 13 ms 14036 KB Output is correct
4 Correct 13 ms 14096 KB Output is correct
5 Correct 13 ms 14036 KB Output is correct
6 Correct 15 ms 13780 KB Output is correct
7 Correct 13 ms 14152 KB Output is correct
8 Correct 16 ms 13776 KB Output is correct
9 Correct 12 ms 13780 KB Output is correct
10 Correct 13 ms 14036 KB Output is correct
11 Correct 12 ms 14600 KB Output is correct
12 Correct 12 ms 13780 KB Output is correct
13 Correct 14 ms 13776 KB Output is correct
14 Correct 13 ms 14036 KB Output is correct
15 Correct 14 ms 14040 KB Output is correct
16 Incorrect 1 ms 8536 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 13 ms 14136 KB Output is correct
3 Correct 13 ms 14036 KB Output is correct
4 Correct 13 ms 14096 KB Output is correct
5 Correct 13 ms 14036 KB Output is correct
6 Correct 15 ms 13780 KB Output is correct
7 Correct 13 ms 14152 KB Output is correct
8 Correct 16 ms 13776 KB Output is correct
9 Correct 12 ms 13780 KB Output is correct
10 Correct 13 ms 14036 KB Output is correct
11 Correct 12 ms 14600 KB Output is correct
12 Correct 12 ms 13780 KB Output is correct
13 Correct 14 ms 13776 KB Output is correct
14 Correct 13 ms 14036 KB Output is correct
15 Correct 14 ms 14040 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Execution timed out 4074 ms 14036 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Incorrect 1 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -