oj.uz

Submission #730371

# Submission time Handle Problem Language Result Execution time Memory
730371 2023-04-25T18:27:39 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 12804 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;
    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, keep);
        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, 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);
    }

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

    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, keep);
        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, 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);
    }

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

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

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 0 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 12 ms 420 KB Output is correct
6 Correct 16 ms 420 KB Output is correct
7 Correct 12 ms 416 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 17 ms 420 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 8 ms 408 KB Output is correct
12 Correct 7 ms 412 KB Output is correct
13 Correct 14 ms 340 KB Output is correct
14 Correct 6 ms 412 KB Output is correct
15 Correct 10 ms 416 KB Output is correct
16 Correct 10 ms 340 KB Output is correct
17 Correct 8 ms 408 KB Output is correct
18 Correct 12 ms 340 KB Output is correct
19 Correct 10 ms 340 KB Output is correct
20 Correct 9 ms 420 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 95 ms 12272 KB Output is correct
3 Correct 83 ms 11848 KB Output is correct
4 Correct 95 ms 12268 KB Output is correct
5 Correct 92 ms 11888 KB Output is correct
6 Correct 68 ms 10228 KB Output is correct
7 Correct 59 ms 9468 KB Output is correct
8 Correct 65 ms 10140 KB Output is correct
9 Correct 52 ms 9432 KB Output is correct
10 Correct 79 ms 10068 KB Output is correct
11 Correct 82 ms 10052 KB Output is correct
12 Correct 81 ms 10108 KB Output is correct
13 Correct 57 ms 10076 KB Output is correct
14 Correct 76 ms 11416 KB Output is correct
15 Correct 71 ms 11352 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 0 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 12 ms 420 KB Output is correct
6 Correct 16 ms 420 KB Output is correct
7 Correct 12 ms 416 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 17 ms 420 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 8 ms 408 KB Output is correct
12 Correct 7 ms 412 KB Output is correct
13 Correct 14 ms 340 KB Output is correct
14 Correct 6 ms 412 KB Output is correct
15 Correct 10 ms 416 KB Output is correct
16 Correct 10 ms 340 KB Output is correct
17 Correct 8 ms 408 KB Output is correct
18 Correct 12 ms 340 KB Output is correct
19 Correct 10 ms 340 KB Output is correct
20 Correct 9 ms 420 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 95 ms 12272 KB Output is correct
23 Correct 83 ms 11848 KB Output is correct
24 Correct 95 ms 12268 KB Output is correct
25 Correct 92 ms 11888 KB Output is correct
26 Correct 68 ms 10228 KB Output is correct
27 Correct 59 ms 9468 KB Output is correct
28 Correct 65 ms 10140 KB Output is correct
29 Correct 52 ms 9432 KB Output is correct
30 Correct 79 ms 10068 KB Output is correct
31 Correct 82 ms 10052 KB Output is correct
32 Correct 81 ms 10108 KB Output is correct
33 Correct 57 ms 10076 KB Output is correct
34 Correct 76 ms 11416 KB Output is correct
35 Correct 71 ms 11352 KB Output is correct
36 Correct 172 ms 12804 KB Output is correct
37 Correct 137 ms 11976 KB Output is correct
38 Correct 140 ms 11596 KB Output is correct
39 Correct 147 ms 12748 KB Output is correct
40 Correct 142 ms 11400 KB Output is correct
41 Correct 94 ms 10288 KB Output is correct
42 Correct 98 ms 10316 KB Output is correct
43 Correct 109 ms 9480 KB Output is correct
44 Correct 131 ms 9652 KB Output is correct
45 Correct 147 ms 10488 KB Output is correct
46 Correct 118 ms 10212 KB Output is correct
47 Correct 115 ms 9356 KB Output is correct
48 Correct 83 ms 10148 KB Output is correct
49 Correct 99 ms 10060 KB Output is correct
50 Correct 125 ms 11364 KB Output is correct
51 Correct 109 ms 11416 KB Output is correct
52 Correct 103 ms 11404 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 95 ms 12272 KB Output is correct
3 Correct 83 ms 11848 KB Output is correct
4 Correct 95 ms 12268 KB Output is correct
5 Correct 92 ms 11888 KB Output is correct
6 Correct 68 ms 10228 KB Output is correct
7 Correct 59 ms 9468 KB Output is correct
8 Correct 65 ms 10140 KB Output is correct
9 Correct 52 ms 9432 KB Output is correct
10 Correct 79 ms 10068 KB Output is correct
11 Correct 82 ms 10052 KB Output is correct
12 Correct 81 ms 10108 KB Output is correct
13 Correct 57 ms 10076 KB Output is correct
14 Correct 76 ms 11416 KB Output is correct
15 Correct 71 ms 11352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4026 ms 12292 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 95 ms 12272 KB Output is correct
3 Correct 83 ms 11848 KB Output is correct
4 Correct 95 ms 12268 KB Output is correct
5 Correct 92 ms 11888 KB Output is correct
6 Correct 68 ms 10228 KB Output is correct
7 Correct 59 ms 9468 KB Output is correct
8 Correct 65 ms 10140 KB Output is correct
9 Correct 52 ms 9432 KB Output is correct
10 Correct 79 ms 10068 KB Output is correct
11 Correct 82 ms 10052 KB Output is correct
12 Correct 81 ms 10108 KB Output is correct
13 Correct 57 ms 10076 KB Output is correct
14 Correct 76 ms 11416 KB Output is correct
15 Correct 71 ms 11352 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3129 ms 12504 KB Output is correct
18 Correct 1670 ms 12624 KB Output is correct
19 Correct 1869 ms 12316 KB Output is correct
20 Correct 1333 ms 12692 KB Output is correct
21 Correct 2967 ms 12620 KB Output is correct
22 Correct 1664 ms 12520 KB Output is correct
23 Correct 2596 ms 12204 KB Output is correct
24 Correct 1573 ms 12624 KB Output is correct
25 Correct 2185 ms 12168 KB Output is correct
26 Correct 765 ms 10492 KB Output is correct
27 Correct 1044 ms 10420 KB Output is correct
28 Correct 1047 ms 11332 KB Output is correct
29 Correct 823 ms 10656 KB Output is correct
30 Correct 1040 ms 10568 KB Output is correct
31 Correct 1349 ms 11404 KB Output is correct
32 Correct 1520 ms 11668 KB Output is correct
33 Correct 879 ms 10152 KB Output is correct
34 Correct 1527 ms 12236 KB Output is correct
35 Correct 749 ms 10204 KB Output is correct
36 Correct 1427 ms 11796 KB Output is correct
37 Correct 772 ms 11352 KB Output is correct
38 Correct 519 ms 11280 KB Output is correct
39 Correct 865 ms 11824 KB Output is correct
40 Correct 471 ms 11812 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 0 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 12 ms 420 KB Output is correct
6 Correct 16 ms 420 KB Output is correct
7 Correct 12 ms 416 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 17 ms 420 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 8 ms 408 KB Output is correct
12 Correct 7 ms 412 KB Output is correct
13 Correct 14 ms 340 KB Output is correct
14 Correct 6 ms 412 KB Output is correct
15 Correct 10 ms 416 KB Output is correct
16 Correct 10 ms 340 KB Output is correct
17 Correct 8 ms 408 KB Output is correct
18 Correct 12 ms 340 KB Output is correct
19 Correct 10 ms 340 KB Output is correct
20 Correct 9 ms 420 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 95 ms 12272 KB Output is correct
23 Correct 83 ms 11848 KB Output is correct
24 Correct 95 ms 12268 KB Output is correct
25 Correct 92 ms 11888 KB Output is correct
26 Correct 68 ms 10228 KB Output is correct
27 Correct 59 ms 9468 KB Output is correct
28 Correct 65 ms 10140 KB Output is correct
29 Correct 52 ms 9432 KB Output is correct
30 Correct 79 ms 10068 KB Output is correct
31 Correct 82 ms 10052 KB Output is correct
32 Correct 81 ms 10108 KB Output is correct
33 Correct 57 ms 10076 KB Output is correct
34 Correct 76 ms 11416 KB Output is correct
35 Correct 71 ms 11352 KB Output is correct
36 Correct 172 ms 12804 KB Output is correct
37 Correct 137 ms 11976 KB Output is correct
38 Correct 140 ms 11596 KB Output is correct
39 Correct 147 ms 12748 KB Output is correct
40 Correct 142 ms 11400 KB Output is correct
41 Correct 94 ms 10288 KB Output is correct
42 Correct 98 ms 10316 KB Output is correct
43 Correct 109 ms 9480 KB Output is correct
44 Correct 131 ms 9652 KB Output is correct
45 Correct 147 ms 10488 KB Output is correct
46 Correct 118 ms 10212 KB Output is correct
47 Correct 115 ms 9356 KB Output is correct
48 Correct 83 ms 10148 KB Output is correct
49 Correct 99 ms 10060 KB Output is correct
50 Correct 125 ms 11364 KB Output is correct
51 Correct 109 ms 11416 KB Output is correct
52 Correct 103 ms 11404 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4026 ms 12292 KB Time limit exceeded
55 Halted 0 ms 0 KB -