oj.uz

Submission #876318

# Submission time Handle Problem Language Result Execution time Memory
876318 2023-11-21T14:32:49 Z danikoynov Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 13008 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)
    {
        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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 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 6488 KB Output is correct
2 Correct 13 ms 12500 KB Output is correct
3 Correct 12 ms 12496 KB Output is correct
4 Correct 14 ms 12488 KB Output is correct
5 Correct 13 ms 12500 KB Output is correct
6 Correct 15 ms 12504 KB Output is correct
7 Correct 12 ms 11988 KB Output is correct
8 Correct 17 ms 12548 KB Output is correct
9 Correct 12 ms 11988 KB Output is correct
10 Correct 13 ms 12500 KB Output is correct
11 Correct 12 ms 12544 KB Output is correct
12 Correct 12 ms 11988 KB Output is correct
13 Correct 12 ms 11988 KB Output is correct
14 Correct 13 ms 12500 KB Output is correct
15 Correct 14 ms 12388 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 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 6488 KB Output is correct
2 Correct 13 ms 12500 KB Output is correct
3 Correct 12 ms 12496 KB Output is correct
4 Correct 14 ms 12488 KB Output is correct
5 Correct 13 ms 12500 KB Output is correct
6 Correct 15 ms 12504 KB Output is correct
7 Correct 12 ms 11988 KB Output is correct
8 Correct 17 ms 12548 KB Output is correct
9 Correct 12 ms 11988 KB Output is correct
10 Correct 13 ms 12500 KB Output is correct
11 Correct 12 ms 12544 KB Output is correct
12 Correct 12 ms 11988 KB Output is correct
13 Correct 12 ms 11988 KB Output is correct
14 Correct 13 ms 12500 KB Output is correct
15 Correct 14 ms 12388 KB Output is correct
16 Incorrect 1 ms 6492 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 6488 KB Output is correct
2 Correct 13 ms 12500 KB Output is correct
3 Correct 12 ms 12496 KB Output is correct
4 Correct 14 ms 12488 KB Output is correct
5 Correct 13 ms 12500 KB Output is correct
6 Correct 15 ms 12504 KB Output is correct
7 Correct 12 ms 11988 KB Output is correct
8 Correct 17 ms 12548 KB Output is correct
9 Correct 12 ms 11988 KB Output is correct
10 Correct 13 ms 12500 KB Output is correct
11 Correct 12 ms 12544 KB Output is correct
12 Correct 12 ms 11988 KB Output is correct
13 Correct 12 ms 11988 KB Output is correct
14 Correct 13 ms 12500 KB Output is correct
15 Correct 14 ms 12388 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Execution timed out 4038 ms 13008 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -