Submission #876481

#	Time	Username	Problem	Language	Result	Execution time	Memory
876481		danikoynov	Fish 2 (JOI22_fish2)	C++14	36 / 100	4066 ms	34464 KiB

fish2

#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;

}

struct interval
{
    int left, right, pivot;

    interval(int _left = 0, int _right = 0, int _pivot = 0)
    {
        left = _left;
        right = _right;
        pivot = _pivot;
    }
    bool operator < (const interval &it) const
    {
        if (left != it.left)
            return left < it.left;
        if (right != it.right)
            return right > it.right;
        ///assert(pivot != it.pivot);
        return pivot < it.pivot;
    }
};

set < interval > ranges;

void get_ranges()
{
    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();

        ranges.insert(interval(st.top(), i, i));

        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();

        ranges.insert(interval(i, st.top(), i));

        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];
int lazy[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 push_lazy(int root, int left, int right)
{
    tree[root].mx += lazy[root];
    if (left != right)
    {
        lazy[root * 2] += lazy[root];
        lazy[root * 2 + 1] += lazy[root];
    }
    lazy[root] = 0;
}

void build_tree(int root, int left, int right)
{
    lazy[root] = 0;
    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]);
}

void update_range(int root, int left, int right, int qleft, int qright, int 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] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
    push_lazy(root, left, right);
    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)
        {
            push_lazy(root * 2, left, mid);
            push_lazy(root * 2 + 1, mid + 1, right);
            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)
        {
            push_lazy(root * 2, left, mid);
            push_lazy(root * 2 + 1, mid + 1, right);
            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, right_tree;

ll fen[maxn];

void update_fen(int pos, ll val)
{
    for (int i = pos; i <= n; i += (i & -i))
        fen[i] += val;
}

ll query_fen(int pos)
{
    ll s = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

ll range_sum(int left, int right)
{
    return query_fen(right) - query_fen(left - 1);
}

void solve_query(int left, int right)
{
    int lb = left_tree.walk_right(1, 1, n, left, right, - query_fen(left - 1));
    int rb = right_tree.walk_left(1, 1, n, left, right, query_fen(right));


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

void restructure()
{
    ///cout << "-------------" << endl;
    get_ranges();
    build_tree(1, 1, n);
    for (interval cur : ranges)
    {
        ll mx = min(a[cur.left], a[cur.right]);
        if (range_sum(cur.left + 1, cur.right - 1) < mx)
        {
            update_range(1, 1, n, cur.left + 1, cur.right - 1, 1);
            ///cout << cur.left << " " << cur.right << endl;
            //for (int i = cur.left + 1; i < cur.right; i ++)
              //  b[i] ++;
        }
    }




}
void simulate()
{
    for (int i = 1; i <= n; i ++)
        update_fen(i, a[i]);
    restructure();

    for (int i = 1; i <= n; i ++)
    {
        values[i] = a[i] - query_fen(i - 1);
    }
    left_tree.build_tree(1, 1, n);

    for (int i = 1; i <= n; i ++)
    {
        values[i] = a[i] + query_fen(i);
    }
    right_tree.build_tree(1, 1, n);
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int idx;
            ll x;
            cin >> idx >> x;
            update_fen(idx, x - a[idx]);
            left_tree.update_range(1, 1, n, idx + 1, n, - (x - a[idx]));
            left_tree.update_range(1, 1, n, idx, idx, (x - a[idx]));
            right_tree.update_range(1, 1, n, idx, n, (x - a[idx]));
            right_tree.update_range(1, 1, n, idx, idx, (x - a[idx]));
            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: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17