oj.uz

Submission #730369

# Submission time Handle Problem Language Result Execution time Memory
730369 2023-04-25T18:15:58 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 14488 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  =  1e6   + 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;
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){
    //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);
}

inline void rem(int l, int r, int x, ll y){
    //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);
}


inline void update(int x, ll y){
    //cerr << "ya here " << x << ' ' << y << '\n';
    if(y == a[x])
        return;
    int i = x;
    ll 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);
        sum += a[i];
        i = seg::get_first(0, n, i, n, sum + 1, 1);
    }

    i = x + 1;
    sum = 0;
    while(i != -1){
        rem(x, i, x, y);
        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);
        sum += a[i];
        i = seg::get_last(0, n, 0, i, sum + 1, 1);
    }

    i = x - 1;
    sum = 0;
    while(i != -1){
        rem(i, x, x, y);
        sum += a[i];
        i = seg::get_last(0, n, 0, i, sum + 1, 1);
    }

    a[x] = y;
    seg::upd(0, n, x, 1);
    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);
        sum += a[i];
        i = seg::get_first(0, n, i, n, sum + 1, 1);
    }

    i = x + 1;
    sum = 0;
    while(i != -1){
        add(x, i);
        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);
        sum += a[i];
        i = seg::get_last(0, n, 0, i, sum + 1, 1);
    }

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

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);
            av.pop_back();
        }
        if(av.size())
            add(av.back(), i);
        av.pb(i);
    }

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

/*
5
6 4 2 2 6
3
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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 15 ms 340 KB Output is correct
6 Correct 24 ms 340 KB Output is correct
7 Correct 14 ms 420 KB Output is correct
8 Correct 33 ms 340 KB Output is correct
9 Correct 27 ms 340 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 12 ms 416 KB Output is correct
12 Correct 8 ms 420 KB Output is correct
13 Correct 24 ms 340 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 13 ms 340 KB Output is correct
16 Correct 16 ms 340 KB Output is correct
17 Correct 9 ms 340 KB Output is correct
18 Correct 17 ms 340 KB Output is correct
19 Correct 9 ms 340 KB Output is correct
20 Correct 12 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 100 ms 12424 KB Output is correct
3 Correct 84 ms 11976 KB Output is correct
4 Correct 100 ms 12436 KB Output is correct
5 Correct 79 ms 12012 KB Output is correct
6 Correct 72 ms 10376 KB Output is correct
7 Correct 51 ms 9568 KB Output is correct
8 Correct 72 ms 10332 KB Output is correct
9 Correct 52 ms 9548 KB Output is correct
10 Correct 66 ms 10200 KB Output is correct
11 Correct 63 ms 10160 KB Output is correct
12 Correct 62 ms 10124 KB Output is correct
13 Correct 60 ms 10164 KB Output is correct
14 Correct 84 ms 11480 KB Output is correct
15 Correct 81 ms 11388 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 15 ms 340 KB Output is correct
6 Correct 24 ms 340 KB Output is correct
7 Correct 14 ms 420 KB Output is correct
8 Correct 33 ms 340 KB Output is correct
9 Correct 27 ms 340 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 12 ms 416 KB Output is correct
12 Correct 8 ms 420 KB Output is correct
13 Correct 24 ms 340 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 13 ms 340 KB Output is correct
16 Correct 16 ms 340 KB Output is correct
17 Correct 9 ms 340 KB Output is correct
18 Correct 17 ms 340 KB Output is correct
19 Correct 9 ms 340 KB Output is correct
20 Correct 12 ms 340 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 100 ms 12424 KB Output is correct
23 Correct 84 ms 11976 KB Output is correct
24 Correct 100 ms 12436 KB Output is correct
25 Correct 79 ms 12012 KB Output is correct
26 Correct 72 ms 10376 KB Output is correct
27 Correct 51 ms 9568 KB Output is correct
28 Correct 72 ms 10332 KB Output is correct
29 Correct 52 ms 9548 KB Output is correct
30 Correct 66 ms 10200 KB Output is correct
31 Correct 63 ms 10160 KB Output is correct
32 Correct 62 ms 10124 KB Output is correct
33 Correct 60 ms 10164 KB Output is correct
34 Correct 84 ms 11480 KB Output is correct
35 Correct 81 ms 11388 KB Output is correct
36 Correct 174 ms 12928 KB Output is correct
37 Correct 161 ms 12000 KB Output is correct
38 Correct 177 ms 11644 KB Output is correct
39 Correct 160 ms 12964 KB Output is correct
40 Correct 213 ms 11724 KB Output is correct
41 Correct 91 ms 10444 KB Output is correct
42 Correct 103 ms 10572 KB Output is correct
43 Correct 155 ms 9652 KB Output is correct
44 Correct 174 ms 9632 KB Output is correct
45 Correct 163 ms 10576 KB Output is correct
46 Correct 134 ms 10452 KB Output is correct
47 Correct 158 ms 9348 KB Output is correct
48 Correct 85 ms 10160 KB Output is correct
49 Correct 124 ms 10380 KB Output is correct
50 Correct 102 ms 11552 KB Output is correct
51 Correct 146 ms 11608 KB Output is correct
52 Correct 117 ms 11588 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 100 ms 12424 KB Output is correct
3 Correct 84 ms 11976 KB Output is correct
4 Correct 100 ms 12436 KB Output is correct
5 Correct 79 ms 12012 KB Output is correct
6 Correct 72 ms 10376 KB Output is correct
7 Correct 51 ms 9568 KB Output is correct
8 Correct 72 ms 10332 KB Output is correct
9 Correct 52 ms 9548 KB Output is correct
10 Correct 66 ms 10200 KB Output is correct
11 Correct 63 ms 10160 KB Output is correct
12 Correct 62 ms 10124 KB Output is correct
13 Correct 60 ms 10164 KB Output is correct
14 Correct 84 ms 11480 KB Output is correct
15 Correct 81 ms 11388 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4075 ms 12140 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 100 ms 12424 KB Output is correct
3 Correct 84 ms 11976 KB Output is correct
4 Correct 100 ms 12436 KB Output is correct
5 Correct 79 ms 12012 KB Output is correct
6 Correct 72 ms 10376 KB Output is correct
7 Correct 51 ms 9568 KB Output is correct
8 Correct 72 ms 10332 KB Output is correct
9 Correct 52 ms 9548 KB Output is correct
10 Correct 66 ms 10200 KB Output is correct
11 Correct 63 ms 10160 KB Output is correct
12 Correct 62 ms 10124 KB Output is correct
13 Correct 60 ms 10164 KB Output is correct
14 Correct 84 ms 11480 KB Output is correct
15 Correct 81 ms 11388 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 3030 ms 12556 KB Output is correct
18 Correct 1606 ms 14408 KB Output is correct
19 Correct 1922 ms 13472 KB Output is correct
20 Correct 1283 ms 14488 KB Output is correct
21 Correct 3030 ms 14064 KB Output is correct
22 Correct 1681 ms 14376 KB Output is correct
23 Correct 2473 ms 13608 KB Output is correct
24 Correct 1473 ms 14384 KB Output is correct
25 Correct 2168 ms 13360 KB Output is correct
26 Correct 719 ms 12912 KB Output is correct
27 Correct 1020 ms 12884 KB Output is correct
28 Correct 1030 ms 13108 KB Output is correct
29 Correct 810 ms 13132 KB Output is correct
30 Correct 966 ms 12976 KB Output is correct
31 Correct 1271 ms 13184 KB Output is correct
32 Correct 1545 ms 13640 KB Output is correct
33 Correct 886 ms 11928 KB Output is correct
34 Correct 1462 ms 14376 KB Output is correct
35 Correct 763 ms 12236 KB Output is correct
36 Correct 1422 ms 13400 KB Output is correct
37 Correct 773 ms 12860 KB Output is correct
38 Correct 505 ms 12644 KB Output is correct
39 Correct 868 ms 13648 KB Output is correct
40 Correct 420 ms 13620 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 15 ms 340 KB Output is correct
6 Correct 24 ms 340 KB Output is correct
7 Correct 14 ms 420 KB Output is correct
8 Correct 33 ms 340 KB Output is correct
9 Correct 27 ms 340 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 12 ms 416 KB Output is correct
12 Correct 8 ms 420 KB Output is correct
13 Correct 24 ms 340 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 13 ms 340 KB Output is correct
16 Correct 16 ms 340 KB Output is correct
17 Correct 9 ms 340 KB Output is correct
18 Correct 17 ms 340 KB Output is correct
19 Correct 9 ms 340 KB Output is correct
20 Correct 12 ms 340 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 100 ms 12424 KB Output is correct
23 Correct 84 ms 11976 KB Output is correct
24 Correct 100 ms 12436 KB Output is correct
25 Correct 79 ms 12012 KB Output is correct
26 Correct 72 ms 10376 KB Output is correct
27 Correct 51 ms 9568 KB Output is correct
28 Correct 72 ms 10332 KB Output is correct
29 Correct 52 ms 9548 KB Output is correct
30 Correct 66 ms 10200 KB Output is correct
31 Correct 63 ms 10160 KB Output is correct
32 Correct 62 ms 10124 KB Output is correct
33 Correct 60 ms 10164 KB Output is correct
34 Correct 84 ms 11480 KB Output is correct
35 Correct 81 ms 11388 KB Output is correct
36 Correct 174 ms 12928 KB Output is correct
37 Correct 161 ms 12000 KB Output is correct
38 Correct 177 ms 11644 KB Output is correct
39 Correct 160 ms 12964 KB Output is correct
40 Correct 213 ms 11724 KB Output is correct
41 Correct 91 ms 10444 KB Output is correct
42 Correct 103 ms 10572 KB Output is correct
43 Correct 155 ms 9652 KB Output is correct
44 Correct 174 ms 9632 KB Output is correct
45 Correct 163 ms 10576 KB Output is correct
46 Correct 134 ms 10452 KB Output is correct
47 Correct 158 ms 9348 KB Output is correct
48 Correct 85 ms 10160 KB Output is correct
49 Correct 124 ms 10380 KB Output is correct
50 Correct 102 ms 11552 KB Output is correct
51 Correct 146 ms 11608 KB Output is correct
52 Correct 117 ms 11588 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4075 ms 12140 KB Time limit exceeded
55 Halted 0 ms 0 KB -