oj.uz

Submission #876331

# Submission time Handle Problem Language Result Execution time Memory
876331 2023-11-21T14:41:19 Z danikoynov Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 14496 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 0;

        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 max(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]);
    lb = max(lb, left);
    /**cout << lb << " " << a[left + 2] - pref[left + 1] << " " << " " << -pref[left - 1] << endl;
    for (int i = 1; i <= n; i ++)
        cout << pref[i] << " ";
    cout << endl;*/

    /**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;
}
/*
12
32 32 4 1 1 1 1 4 4 16 32 128
1
2 8 10

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 8 ms 8540 KB Output is correct
6 Incorrect 4 ms 8708 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 13 ms 14036 KB Output is correct
3 Correct 12 ms 14036 KB Output is correct
4 Correct 13 ms 14040 KB Output is correct
5 Correct 13 ms 14044 KB Output is correct
6 Correct 15 ms 13704 KB Output is correct
7 Correct 12 ms 13776 KB Output is correct
8 Correct 16 ms 13616 KB Output is correct
9 Correct 12 ms 13800 KB Output is correct
10 Correct 14 ms 14036 KB Output is correct
11 Correct 13 ms 14288 KB Output is correct
12 Correct 14 ms 13780 KB Output is correct
13 Correct 14 ms 13780 KB Output is correct
14 Correct 16 ms 14080 KB Output is correct
15 Correct 14 ms 14036 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 8 ms 8540 KB Output is correct
6 Incorrect 4 ms 8708 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 13 ms 14036 KB Output is correct
3 Correct 12 ms 14036 KB Output is correct
4 Correct 13 ms 14040 KB Output is correct
5 Correct 13 ms 14044 KB Output is correct
6 Correct 15 ms 13704 KB Output is correct
7 Correct 12 ms 13776 KB Output is correct
8 Correct 16 ms 13616 KB Output is correct
9 Correct 12 ms 13800 KB Output is correct
10 Correct 14 ms 14036 KB Output is correct
11 Correct 13 ms 14288 KB Output is correct
12 Correct 14 ms 13780 KB Output is correct
13 Correct 14 ms 13780 KB Output is correct
14 Correct 16 ms 14080 KB Output is correct
15 Correct 14 ms 14036 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Incorrect 2285 ms 14496 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 13 ms 14036 KB Output is correct
3 Correct 12 ms 14036 KB Output is correct
4 Correct 13 ms 14040 KB Output is correct
5 Correct 13 ms 14044 KB Output is correct
6 Correct 15 ms 13704 KB Output is correct
7 Correct 12 ms 13776 KB Output is correct
8 Correct 16 ms 13616 KB Output is correct
9 Correct 12 ms 13800 KB Output is correct
10 Correct 14 ms 14036 KB Output is correct
11 Correct 13 ms 14288 KB Output is correct
12 Correct 14 ms 13780 KB Output is correct
13 Correct 14 ms 13780 KB Output is correct
14 Correct 16 ms 14080 KB Output is correct
15 Correct 14 ms 14036 KB Output is correct
16 Correct 1 ms 8536 KB Output is correct
17 Execution timed out 4058 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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 8 ms 8540 KB Output is correct
6 Incorrect 4 ms 8708 KB Output isn't correct
7 Halted 0 ms 0 KB -