oj.uz

Submission #730377

# Submission time Handle Problem Language Result Execution time Memory
730377 2023-04-25T18:42:39 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 12880 KB 
// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  2e7   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  5e5   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;


set <pii> have;
ll a[maxn5];
int n, undopt = 0;
pii ch[maxn];
vector <ll> av;

namespace seg{

    pii mn[maxnt];
    int lazy[maxnt];
    ll sum[maxnt], mx[maxnt];

    inline pii comb(pii a, pii b){
        pii ans = min(a, b);
        if(a.fi == b.fi)
            ans.se = a.se + b.se;
        return ans;
    }

    void build(int l, int r, int v){
        mn[v] = {0, r - l};
        if(r - l == 1)
            return;
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
    }

    void upd(int l, int r, int id, int v){
        if(r - l == 1){
            mx[v] = sum[v] = a[id];
            return;
        }
        int mid = (l + r) >> 1;
        if(id < mid)
            upd(l, mid, id, v * 2);
        else
            upd(mid, r, id, v * 2 + 1);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
        sum[v] = sum[v * 2] + sum[v * 2 + 1];
    }

    void add(int l, int r, int lq, int rq, int val, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] += val;
            mn[v].fi += val;
            return;
        }
        int mid = (l + r) >> 1;
        add(l, mid, lq, rq, val, v * 2);
        add(mid, r, lq, rq, val, v * 2 + 1);
        mn[v] = comb(mn[v * 2], mn[v * 2 + 1]);
        mn[v].fi += lazy[v];
    }

    ll get_sum(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return 0;
        if(lq <= l && r <= rq)
            return sum[v];
        int mid = (l + r) >> 1;
        return get_sum(l, mid, lq, rq, v * 2) + get_sum(mid, r, lq, rq, v * 2 + 1);
    }

    pii get_min(int l, int r, int lq, int rq, int v){
        if(rq <= l || r <= lq)
            return {mod, 0};
        if(lq <= l && r <= rq)
            return mn[v];
        int mid = (l + r) >> 1;
        pii ans = comb(get_min(l, mid, lq, rq, v * 2), get_min(mid, r, lq, rq, v * 2 + 1));
        ans.fi += lazy[v];
        return ans;
    }

    int get_first(int l, int r, int lq, int rq, ll val, int v){
        if(rq <= l || r <= lq || mx[v] < val)
            return -1;
        if(r - l == 1)
            return l;
        int mid = (l + r) >> 1;
        int ans = get_first(l, mid, lq, rq, val, v * 2);
        if(ans != -1)
            return ans;
        return get_first(mid, r, lq, rq, val, v * 2 + 1);
    }

    int get_last(int l, int r, int lq, int rq, ll val, int v){
        if(rq <= l || r <= lq || mx[v] < val)
            return -1;
        if(r - l == 1)
            return l;
        int mid = (l + r) >> 1;
        int ans = get_last(mid, r, lq, rq, val, v * 2 + 1);
        if(ans != -1)
            return ans;
        return get_last(l, mid, lq, rq, val, v * 2);
    }

}


inline void add(int l, int r, bool keep){
    //cerr << "checking for add " << l << ' ' << r << '\n';
    if(l + 1 == r || have.find({l, r}) != have.end())
        return;
    if(have.find({l, r}) != have.end())
        return;
    ll sum = seg::get_sum(0, n, l + 1, r, 1);
    if(sum >= min(a[l], a[r]))
        return;
    //cerr << "will be added " << '\n';
    have.insert({l, r});
    seg::add(0, n, l + 1, r, 1, 1);
    if(keep)
        ch[undopt++] = {l, -r};
}

inline void rem(int l, int r, int x, ll y, bool keep){
    //cerr << "checking for remove " << l << ' ' << r << ' ' << x << ' ' << y << '\n';
    if(l + 1 == r || have.find({l, r}) == have.end())
        return;
    ll sum = seg::get_sum(0, n, l + 1, r, 1);
    if(x > l && x < r)
        sum += y - a[x];
    //cerr << "it's " << sum << '\n';
    if(sum < min(l == x ? y : a[l], r == x ? y : a[r]))
        return;
    //cerr << "ya will be removed " << '\n';
    have.erase({l, r});
    seg::add(0, n, l + 1, r, -1, 1);
    if(keep)
        ch[undopt++] = {l, r};
}


inline void update(int x, ll y, bool keep){
    //cerr << "ya here " << x << ' ' << y << '\n';
    if(y == a[x])
        return;
    ll sum; int i;
    if(y > a[x]){
        i = x;
        sum = 0;
        while(i != -1){
            int id = seg::get_last(0, n, 0, i, a[i], 1);
            if(id != -1 && id <= x)
                rem(id, i, x, y, keep);
            sum += a[i];
            i = seg::get_first(0, n, i, n, sum + 1, 1);
        }

        i = x;
        sum = 0;
        while(i != -1){
            int id = seg::get_first(0, n, i + 1, n, a[i], 1);
            if(id != -1 && id >= x)
                rem(i, id, x, y, keep);
            sum += a[i];
            i = seg::get_last(0, n, 0, i, sum + 1, 1);
        }
    }
    else{
        i = x + 1;
        sum = 0;
        while(i != -1){
            rem(x, i, x, y, keep);
            sum += a[i];
            i = seg::get_first(0, n, i, n, sum + 1, 1);
        }
        i = x - 1;
        sum = 0;
        while(i != -1){
            rem(i, x, x, y, keep);
            sum += a[i];
            i = seg::get_last(0, n, 0, i, sum + 1, 1);
        }
    }
    ll kp = a[x];
    a[x] = y;
    seg::upd(0, n, x, 1);
    if(y > kp){
        i = x + 1;
        sum = 0;
        while(i != -1){
            add(x, i, keep);
            sum += a[i];
            i = seg::get_first(0, n, i, n, sum + 1, 1);
        }

        i = x - 1;
        sum = 0;
        while(i != -1){
            add(i, x, keep);
            sum += a[i];
            //cerr << "here " << i << ' ' << sum << endl;
            i = seg::get_last(0, n, 0, i, sum + 1, 1);
            //cerr << "hmmmmm " << i << ' ' << sum << endl;
        }
    }
    else{
        i = x;
        sum = 0;
        while(i != -1){
            int id = seg::get_last(0, n, 0, i, a[i], 1);
            if(id != -1 && id <= x)
                add(id, i, keep);
            sum += a[i];
            i = seg::get_first(0, n, i, n, sum + 1, 1);
        }


        i = x;
        sum = 0;
        while(i != -1){
            int id = seg::get_first(0, n, i + 1, n, a[i], 1);
            if(id != -1 && id >= x)
                add(i, id, keep);
            sum += a[i];
            i = seg::get_last(0, n, 0, i, sum + 1, 1);
        }


    }
}

inline void undo(){
    for(int i = undopt - 1; i >= 0; i--){
        int l = ch[i].fi, r = ch[i].se;
        if(r == 0)
            continue;
        if(r < 0){
            r *= -1;
            seg::add(0, n, l + 1, r, -1, 1);
            have.erase({l, r});
        }
        else{
            seg::add(0, n, l + 1, r, 1, 1);
            have.insert({l, r});
        }
    }
    undopt = 0;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);


    cin >> n;
    n += 2;
    seg::build(0, n, 1);
    a[0] = a[n - 1] = inf;
    av.pb(0);
    seg::upd(0, n, 0, 1);
    for(int i = 1; i < n; i++){
        if(i < n - 1)
            cin >> a[i];
        seg::upd(0, n, i, 1);
        while(av.size() && a[av.back()] <= a[i]){
            add(av.back(), i, false);
            av.pop_back();
        }
        if(av.size())
            add(av.back(), i, false);
        av.pb(i);
    }

    int q; cin >> q;
    while(q--){
        int ty, x, y; cin >> ty >> x >> y;
        if(ty == 1)
            update(x, y, false);
        else{
            ll keepx = a[x - 1], keepy = a[y + 1];
            undopt = 0;
            update(x - 1, inf, true);
            update(y + 1, inf, true);
            cout << seg::get_min(0, n, x, y + 1, 1).se << '\n';
            a[x - 1] = keepx;
            a[y + 1] = keepy;
            seg::upd(0, n, x - 1, 1);
            seg::upd(0, n, y + 1, 1);
            undo();
        }
    }
}

/*
5
6 4 2 2 6
3
1 3 1
2 2 5
2 1 5
2 2 4

5
6 4 2 2 6
1
2 1 3
2 1 5
1 3 1
2 2 5
2 1 5
2 2 4

3
6 4 2
1
2 1 2

10
2 3 5 10 1 3 4 9 5 2
2
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10 
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 14 ms 420 KB Output is correct
7 Correct 10 ms 416 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 15 ms 420 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 12 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 9 ms 340 KB Output is correct
17 Correct 7 ms 340 KB Output is correct
18 Correct 9 ms 416 KB Output is correct
19 Correct 6 ms 416 KB Output is correct
20 Correct 7 ms 416 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 103 ms 12312 KB Output is correct
3 Correct 77 ms 11832 KB Output is correct
4 Correct 98 ms 12284 KB Output is correct
5 Correct 77 ms 11840 KB Output is correct
6 Correct 62 ms 10144 KB Output is correct
7 Correct 56 ms 9460 KB Output is correct
8 Correct 63 ms 10232 KB Output is correct
9 Correct 53 ms 9496 KB Output is correct
10 Correct 61 ms 10100 KB Output is correct
11 Correct 64 ms 10056 KB Output is correct
12 Correct 55 ms 10028 KB Output is correct
13 Correct 61 ms 10056 KB Output is correct
14 Correct 92 ms 11436 KB Output is correct
15 Correct 74 ms 11316 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 14 ms 420 KB Output is correct
7 Correct 10 ms 416 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 15 ms 420 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 12 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 9 ms 340 KB Output is correct
17 Correct 7 ms 340 KB Output is correct
18 Correct 9 ms 416 KB Output is correct
19 Correct 6 ms 416 KB Output is correct
20 Correct 7 ms 416 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 103 ms 12312 KB Output is correct
23 Correct 77 ms 11832 KB Output is correct
24 Correct 98 ms 12284 KB Output is correct
25 Correct 77 ms 11840 KB Output is correct
26 Correct 62 ms 10144 KB Output is correct
27 Correct 56 ms 9460 KB Output is correct
28 Correct 63 ms 10232 KB Output is correct
29 Correct 53 ms 9496 KB Output is correct
30 Correct 61 ms 10100 KB Output is correct
31 Correct 64 ms 10056 KB Output is correct
32 Correct 55 ms 10028 KB Output is correct
33 Correct 61 ms 10056 KB Output is correct
34 Correct 92 ms 11436 KB Output is correct
35 Correct 74 ms 11316 KB Output is correct
36 Correct 150 ms 12880 KB Output is correct
37 Correct 124 ms 11992 KB Output is correct
38 Correct 160 ms 11520 KB Output is correct
39 Correct 152 ms 12772 KB Output is correct
40 Correct 133 ms 11500 KB Output is correct
41 Correct 84 ms 10368 KB Output is correct
42 Correct 87 ms 10316 KB Output is correct
43 Correct 101 ms 9548 KB Output is correct
44 Correct 122 ms 9520 KB Output is correct
45 Correct 131 ms 10624 KB Output is correct
46 Correct 124 ms 10180 KB Output is correct
47 Correct 114 ms 9164 KB Output is correct
48 Correct 74 ms 10120 KB Output is correct
49 Correct 92 ms 10056 KB Output is correct
50 Correct 90 ms 11456 KB Output is correct
51 Correct 94 ms 11384 KB Output is correct
52 Correct 93 ms 11460 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 103 ms 12312 KB Output is correct
3 Correct 77 ms 11832 KB Output is correct
4 Correct 98 ms 12284 KB Output is correct
5 Correct 77 ms 11840 KB Output is correct
6 Correct 62 ms 10144 KB Output is correct
7 Correct 56 ms 9460 KB Output is correct
8 Correct 63 ms 10232 KB Output is correct
9 Correct 53 ms 9496 KB Output is correct
10 Correct 61 ms 10100 KB Output is correct
11 Correct 64 ms 10056 KB Output is correct
12 Correct 55 ms 10028 KB Output is correct
13 Correct 61 ms 10056 KB Output is correct
14 Correct 92 ms 11436 KB Output is correct
15 Correct 74 ms 11316 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4040 ms 12328 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 103 ms 12312 KB Output is correct
3 Correct 77 ms 11832 KB Output is correct
4 Correct 98 ms 12284 KB Output is correct
5 Correct 77 ms 11840 KB Output is correct
6 Correct 62 ms 10144 KB Output is correct
7 Correct 56 ms 9460 KB Output is correct
8 Correct 63 ms 10232 KB Output is correct
9 Correct 53 ms 9496 KB Output is correct
10 Correct 61 ms 10100 KB Output is correct
11 Correct 64 ms 10056 KB Output is correct
12 Correct 55 ms 10028 KB Output is correct
13 Correct 61 ms 10056 KB Output is correct
14 Correct 92 ms 11436 KB Output is correct
15 Correct 74 ms 11316 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1936 ms 12384 KB Output is correct
18 Correct 1191 ms 12556 KB Output is correct
19 Correct 1323 ms 12200 KB Output is correct
20 Correct 1006 ms 12872 KB Output is correct
21 Correct 1805 ms 12484 KB Output is correct
22 Correct 1258 ms 12492 KB Output is correct
23 Correct 1536 ms 12220 KB Output is correct
24 Correct 1114 ms 12560 KB Output is correct
25 Correct 1379 ms 12072 KB Output is correct
26 Correct 449 ms 10524 KB Output is correct
27 Correct 620 ms 10468 KB Output is correct
28 Correct 733 ms 11596 KB Output is correct
29 Correct 513 ms 10444 KB Output is correct
30 Correct 641 ms 10448 KB Output is correct
31 Correct 906 ms 11540 KB Output is correct
32 Correct 1091 ms 11660 KB Output is correct
33 Correct 477 ms 10136 KB Output is correct
34 Correct 1074 ms 12104 KB Output is correct
35 Correct 424 ms 10492 KB Output is correct
36 Correct 930 ms 11864 KB Output is correct
37 Correct 558 ms 11468 KB Output is correct
38 Correct 374 ms 11276 KB Output is correct
39 Correct 566 ms 11704 KB Output is correct
40 Correct 306 ms 11964 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 14 ms 420 KB Output is correct
7 Correct 10 ms 416 KB Output is correct
8 Correct 22 ms 340 KB Output is correct
9 Correct 15 ms 420 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 6 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 12 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 9 ms 340 KB Output is correct
17 Correct 7 ms 340 KB Output is correct
18 Correct 9 ms 416 KB Output is correct
19 Correct 6 ms 416 KB Output is correct
20 Correct 7 ms 416 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 103 ms 12312 KB Output is correct
23 Correct 77 ms 11832 KB Output is correct
24 Correct 98 ms 12284 KB Output is correct
25 Correct 77 ms 11840 KB Output is correct
26 Correct 62 ms 10144 KB Output is correct
27 Correct 56 ms 9460 KB Output is correct
28 Correct 63 ms 10232 KB Output is correct
29 Correct 53 ms 9496 KB Output is correct
30 Correct 61 ms 10100 KB Output is correct
31 Correct 64 ms 10056 KB Output is correct
32 Correct 55 ms 10028 KB Output is correct
33 Correct 61 ms 10056 KB Output is correct
34 Correct 92 ms 11436 KB Output is correct
35 Correct 74 ms 11316 KB Output is correct
36 Correct 150 ms 12880 KB Output is correct
37 Correct 124 ms 11992 KB Output is correct
38 Correct 160 ms 11520 KB Output is correct
39 Correct 152 ms 12772 KB Output is correct
40 Correct 133 ms 11500 KB Output is correct
41 Correct 84 ms 10368 KB Output is correct
42 Correct 87 ms 10316 KB Output is correct
43 Correct 101 ms 9548 KB Output is correct
44 Correct 122 ms 9520 KB Output is correct
45 Correct 131 ms 10624 KB Output is correct
46 Correct 124 ms 10180 KB Output is correct
47 Correct 114 ms 9164 KB Output is correct
48 Correct 74 ms 10120 KB Output is correct
49 Correct 92 ms 10056 KB Output is correct
50 Correct 90 ms 11456 KB Output is correct
51 Correct 94 ms 11384 KB Output is correct
52 Correct 93 ms 11460 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4040 ms 12328 KB Time limit exceeded
55 Halted 0 ms 0 KB -