oj.uz

Submission #876502

# Submission time Handle Problem Language Result Execution time Memory
876502 2023-11-21T20:48:15 Z danikoynov Fish 2 (JOI22_fish2) C++14
36 / 100
 4000 ms 90088 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;

}

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;
set < interval > act[4 * maxn];

void add_range(int root, int left, int right, int qleft, int qright, interval cur)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        //cout << "ROOT " << root << endl;
        act[root].insert(cur);

        return;
    }

    int mid = (left + right) / 2;
    add_range(root * 2, left, mid, qleft, qright, cur);
    add_range(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}

void rem_range(int root, int left, int right, int qleft, int qright, interval cur)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        /**if (act[root].back().left != cur.left || act[root].back().right != cur.right ||
                act[root].back().pivot != cur.pivot)
        {
            cout << "Alert!!!" << endl;
            cout << act[root].back().left <<  " : " << act[root].back().right << " : " << act[root].back().pivot << endl;
            exit(0);
        }*/
        //if (act[root].size() == 0)
          //  cout << "FUCK " << root << endl;
        assert(act[root].size() > 0);
        act[root].erase(cur);
        return;
    }

    int mid = (left + right) / 2;
    rem_range(root * 2, left, mid, qleft, qright, cur);
    rem_range(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}

bool cmp_interval(const interval &it1, const interval &it2)
{
    if ((it1.right - it1.left) != (it2.right - it2.left))
        return (it1.right - it1.left) < (it2.right - it2.left);
    if (it1.left != it2.left)
        return it1.left < it2.left;

    /**if (it1.pivot == it2.pivot)
    {
        cout << "here" << endl;
        cout << it1.left << " " << it1.right << " " << it1.pivot << endl;
        cout << it2.left << " " << it2.right << " " << it2.pivot << endl;
        cout << "FUCK" << endl;
        exit(0);
    }*/
    return (it1.pivot < it2.pivot);
}

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

        ranges.insert(interval(st.top(), i, i));
        vec.push_back(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));
        vec.push_back(interval(i, st.top(), i));

        st.push(i);
    }

    sort(vec.begin(), vec.end(), cmp_interval);
    ///reverse(vec.begin(), vec.end());
    for (interval cur : vec)
    {
        //cout << "added " << cur.left << " " << cur.right << endl;
        add_range(1, 0, n + 1, cur.left, cur.right, cur);
    }
}

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;

    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 fix_point(int pos)
{

    vector < pair < int, int > > to_fix;
    int root = 1, left = 0, right = n + 1;
    vector < interval > to_rem;
    while(true)
    {
        for (interval cur : act[root])
        {
            to_rem.push_back(cur);
            if (cur.pivot == cur.left)
                to_fix.push_back({cur.pivot, 0});
            else
                to_fix.push_back({cur.pivot, 1});
        }
        if (left == right)
            break;
        int mid = (left + right) / 2;
        if (pos <= mid)
            right = mid, root *= 2;
        else
            left = mid + 1, root = (root * 2) + 1;
    }

    sort(to_rem.begin(), to_rem.end(), cmp_interval);
    reverse(to_rem.begin(), to_rem.end());
    for (interval cur : to_rem)
    {
        //cout << "remove " << cur.left << " " << cur.right << endl;
       // if (ranges.find(cur) == ranges.end())
          //  cout << "yep" << endl;
        ranges.erase(cur);
        rem_range(1, 0, n + 1, cur.left, cur.right, cur);
    }



    vector < interval > to_add;
    for (pair < int, int > cur : to_fix)
    {
        if (cur.second == 0)
        {
            int df = cur.first + 1;
            while(a[df] < a[cur.first])
                df ++;
            to_add.push_back(interval(cur.first, df, cur.first));
        }
        else
        {
            int df = cur.first - 1;
            while(a[df] < a[cur.first])
                df --;
            to_add.push_back(interval(df, cur.first, cur.first));
        }
    }

    sort(to_add.begin(), to_add.end(), cmp_interval);
    ///reverse(to_add.begin(), to_add.end());
    for (interval cur : to_add)
    {

        ranges.insert(cur);
        ///cout << "added " << cur.left << " : " << cur.right << endl;
        add_range(1, 0, n + 1, cur.left, cur.right, cur);
    }
}
void simulate()
{
    for (int i = 1; i <= n; i ++)
        update_fen(i, a[i]);
    get_ranges();
    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;
            fix_point(idx);
            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()
{
    //freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}
/*
12
32 32 4 1 1 1 1 4 4 16 32 128
1
2 8 10


*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35164 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 7 ms 35164 KB Output is correct
5 Correct 68 ms 35572 KB Output is correct
6 Correct 24 ms 35416 KB Output is correct
7 Correct 81 ms 35420 KB Output is correct
8 Correct 43 ms 35564 KB Output is correct
9 Correct 27 ms 35420 KB Output is correct
10 Correct 54 ms 35552 KB Output is correct
11 Correct 14 ms 35416 KB Output is correct
12 Correct 73 ms 35536 KB Output is correct
13 Correct 25 ms 35420 KB Output is correct
14 Correct 70 ms 35596 KB Output is correct
15 Correct 56 ms 35420 KB Output is correct
16 Correct 25 ms 35420 KB Output is correct
17 Correct 62 ms 35420 KB Output is correct
18 Correct 14 ms 35420 KB Output is correct
19 Correct 51 ms 35548 KB Output is correct
20 Correct 23 ms 35420 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 262 ms 88604 KB Output is correct
3 Correct 221 ms 84932 KB Output is correct
4 Correct 241 ms 88516 KB Output is correct
5 Correct 228 ms 85444 KB Output is correct
6 Correct 215 ms 80988 KB Output is correct
7 Correct 188 ms 79724 KB Output is correct
8 Correct 206 ms 80976 KB Output is correct
9 Correct 194 ms 79752 KB Output is correct
10 Correct 239 ms 89800 KB Output is correct
11 Correct 210 ms 83320 KB Output is correct
12 Correct 195 ms 79616 KB Output is correct
13 Correct 190 ms 79372 KB Output is correct
14 Correct 187 ms 79208 KB Output is correct
15 Correct 196 ms 79304 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35164 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 7 ms 35164 KB Output is correct
5 Correct 68 ms 35572 KB Output is correct
6 Correct 24 ms 35416 KB Output is correct
7 Correct 81 ms 35420 KB Output is correct
8 Correct 43 ms 35564 KB Output is correct
9 Correct 27 ms 35420 KB Output is correct
10 Correct 54 ms 35552 KB Output is correct
11 Correct 14 ms 35416 KB Output is correct
12 Correct 73 ms 35536 KB Output is correct
13 Correct 25 ms 35420 KB Output is correct
14 Correct 70 ms 35596 KB Output is correct
15 Correct 56 ms 35420 KB Output is correct
16 Correct 25 ms 35420 KB Output is correct
17 Correct 62 ms 35420 KB Output is correct
18 Correct 14 ms 35420 KB Output is correct
19 Correct 51 ms 35548 KB Output is correct
20 Correct 23 ms 35420 KB Output is correct
21 Correct 7 ms 35164 KB Output is correct
22 Correct 262 ms 88604 KB Output is correct
23 Correct 221 ms 84932 KB Output is correct
24 Correct 241 ms 88516 KB Output is correct
25 Correct 228 ms 85444 KB Output is correct
26 Correct 215 ms 80988 KB Output is correct
27 Correct 188 ms 79724 KB Output is correct
28 Correct 206 ms 80976 KB Output is correct
29 Correct 194 ms 79752 KB Output is correct
30 Correct 239 ms 89800 KB Output is correct
31 Correct 210 ms 83320 KB Output is correct
32 Correct 195 ms 79616 KB Output is correct
33 Correct 190 ms 79372 KB Output is correct
34 Correct 187 ms 79208 KB Output is correct
35 Correct 196 ms 79304 KB Output is correct
36 Execution timed out 4032 ms 88520 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 262 ms 88604 KB Output is correct
3 Correct 221 ms 84932 KB Output is correct
4 Correct 241 ms 88516 KB Output is correct
5 Correct 228 ms 85444 KB Output is correct
6 Correct 215 ms 80988 KB Output is correct
7 Correct 188 ms 79724 KB Output is correct
8 Correct 206 ms 80976 KB Output is correct
9 Correct 194 ms 79752 KB Output is correct
10 Correct 239 ms 89800 KB Output is correct
11 Correct 210 ms 83320 KB Output is correct
12 Correct 195 ms 79616 KB Output is correct
13 Correct 190 ms 79372 KB Output is correct
14 Correct 187 ms 79208 KB Output is correct
15 Correct 196 ms 79304 KB Output is correct
16 Correct 6 ms 35160 KB Output is correct
17 Correct 377 ms 85412 KB Output is correct
18 Correct 372 ms 88328 KB Output is correct
19 Correct 369 ms 85432 KB Output is correct
20 Correct 402 ms 85188 KB Output is correct
21 Correct 366 ms 85444 KB Output is correct
22 Correct 373 ms 88776 KB Output is correct
23 Correct 395 ms 85184 KB Output is correct
24 Correct 425 ms 85448 KB Output is correct
25 Correct 399 ms 85400 KB Output is correct
26 Correct 394 ms 85876 KB Output is correct
27 Correct 341 ms 81496 KB Output is correct
28 Correct 336 ms 81692 KB Output is correct
29 Correct 328 ms 81560 KB Output is correct
30 Correct 338 ms 80068 KB Output is correct
31 Correct 336 ms 79812 KB Output is correct
32 Correct 388 ms 83132 KB Output is correct
33 Correct 374 ms 90088 KB Output is correct
34 Correct 402 ms 82888 KB Output is correct
35 Correct 354 ms 82120 KB Output is correct
36 Correct 386 ms 90028 KB Output is correct
37 Correct 345 ms 79768 KB Output is correct
38 Correct 344 ms 79896 KB Output is correct
39 Correct 334 ms 79772 KB Output is correct
40 Correct 360 ms 79988 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35164 KB Output is correct
2 Correct 262 ms 88604 KB Output is correct
3 Correct 221 ms 84932 KB Output is correct
4 Correct 241 ms 88516 KB Output is correct
5 Correct 228 ms 85444 KB Output is correct
6 Correct 215 ms 80988 KB Output is correct
7 Correct 188 ms 79724 KB Output is correct
8 Correct 206 ms 80976 KB Output is correct
9 Correct 194 ms 79752 KB Output is correct
10 Correct 239 ms 89800 KB Output is correct
11 Correct 210 ms 83320 KB Output is correct
12 Correct 195 ms 79616 KB Output is correct
13 Correct 190 ms 79372 KB Output is correct
14 Correct 187 ms 79208 KB Output is correct
15 Correct 196 ms 79304 KB Output is correct
16 Correct 6 ms 35160 KB Output is correct
17 Execution timed out 4070 ms 88668 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35164 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 7 ms 35164 KB Output is correct
5 Correct 68 ms 35572 KB Output is correct
6 Correct 24 ms 35416 KB Output is correct
7 Correct 81 ms 35420 KB Output is correct
8 Correct 43 ms 35564 KB Output is correct
9 Correct 27 ms 35420 KB Output is correct
10 Correct 54 ms 35552 KB Output is correct
11 Correct 14 ms 35416 KB Output is correct
12 Correct 73 ms 35536 KB Output is correct
13 Correct 25 ms 35420 KB Output is correct
14 Correct 70 ms 35596 KB Output is correct
15 Correct 56 ms 35420 KB Output is correct
16 Correct 25 ms 35420 KB Output is correct
17 Correct 62 ms 35420 KB Output is correct
18 Correct 14 ms 35420 KB Output is correct
19 Correct 51 ms 35548 KB Output is correct
20 Correct 23 ms 35420 KB Output is correct
21 Correct 7 ms 35164 KB Output is correct
22 Correct 262 ms 88604 KB Output is correct
23 Correct 221 ms 84932 KB Output is correct
24 Correct 241 ms 88516 KB Output is correct
25 Correct 228 ms 85444 KB Output is correct
26 Correct 215 ms 80988 KB Output is correct
27 Correct 188 ms 79724 KB Output is correct
28 Correct 206 ms 80976 KB Output is correct
29 Correct 194 ms 79752 KB Output is correct
30 Correct 239 ms 89800 KB Output is correct
31 Correct 210 ms 83320 KB Output is correct
32 Correct 195 ms 79616 KB Output is correct
33 Correct 190 ms 79372 KB Output is correct
34 Correct 187 ms 79208 KB Output is correct
35 Correct 196 ms 79304 KB Output is correct
36 Execution timed out 4032 ms 88520 KB Time limit exceeded
37 Halted 0 ms 0 KB -