oj.uz

Submission #730903

# Submission time Handle Problem Language Result Execution time Memory
730903 2023-04-26T15:17:42 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 11036 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;
 
 
ll a[maxn5];
int n, chpt = 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 update(int x, ll y, bool keep){
    //cerr << "ya here " << x << ' ' << y << '\n';
    if(y == a[x])
        return;
    if(y > a[x]){
        ll sum1 = a[x], sum2 = a[x];
        int i1 = seg::get_last(0, n, 0, x, a[x] + 1, 1);
        int i2 = seg::get_first(0, n, x + 1, n, a[x] + 1, 1);
        while(i1 != -1 && i2 != -1){
            ll sum = seg::get_sum(0, n, i1 + 1, i2, 1);
            if(sum < min(a[i1], a[i2]) && sum - a[x] + y >= min(a[i1], a[i2])){
                seg::add(0, n, i1 + 1, i2, -1, 1);
                if(keep)
                    ch[chpt++] = {i1, i2};
            }
            if(a[i1] <= a[i2]){
                sum1 += a[i1];
                i1 = seg::get_last(0, n, 0, i1, sum1 + 1, 1);
            }
            else{
                sum2 += a[i2];
                i2 = seg::get_first(0, n, i2, n, sum2 + 1, 1);
            }
        }
        ll sum = 0;
        int i = seg::get_first(0, n, x + 1, n, a[x], 1);
        while(i != -1){
            ll have = seg::get_sum(0, n, x + 1, i, 1);
            if(have >= min(a[x], a[i]) && have < min(y, a[i])){
                seg::add(0, n, x + 1, i, 1, 1);
                if(keep)
                    ch[chpt++] = {x, -i};
            }
            sum += a[i];
            i = seg::get_first(0, n, i + 1, n, sum + 1, 1);
        }
        sum = 0;
        i = seg::get_last(0, n, 0, x, a[x], 1);
        while(i != -1){
            ll have = seg::get_sum(0, n, i + 1, x, 1);
            if(have >= min(a[x], a[i]) && have < min(y, a[i])){
                seg::add(0, n, i + 1, x, 1, 1);
                if(keep)
                    ch[chpt++] = {i, -x};
            }
            sum += a[i];
            i = seg::get_last(0, n, 0, i, sum + 1, 1);
        }
        a[x] = y;
        seg::upd(0, n, x, 1);
        return;
    }

    ll sum1 = y, sum2 = y;
    int i1 = seg::get_last(0, n, 0, x, y + 1, 1);
    int i2 = seg::get_first(0, n, x + 1, n, y + 1, 1);
    while(i1 != -1 && i2 != -1){
        ll sum = seg::get_sum(0, n, i1 + 1, i2, 1);
        if(sum >= min(a[i1], a[i2]) && sum - a[x] + y < min(a[i1], a[i2])){
            seg::add(0, n, i1 + 1, i2, 1, 1);
            if(keep)
                ch[chpt++] = {i1, -i2};
        }
        if(a[i1] <= a[i2]){
            sum1 += a[i1];
            i1 = seg::get_last(0, n, 0, i1, sum1 + 1, 1);
        }
        else{
            sum2 += a[i2];
            i2 = seg::get_first(0, n, i2, n, sum2 + 1, 1);
        }
    }
    ll sum = 0;
    int i = x + 1;
    while(i != -1){
        ll have = seg::get_sum(0, n, x + 1, i, 1);
        if(have < min(a[x], a[i]) && have >= min(y, a[i])){
            seg::add(0, n, x + 1, i, -1, 1);
            if(keep)
                ch[chpt++] = {x, i};
        }
        sum += a[i];
        i = seg::get_first(0, n, i + 1, n, sum + 1, 1);
    }
    sum = 0;
    i = x - 1;
    while(i != -1){
        ll have = seg::get_sum(0, n, i + 1, x, 1);
        if(have < min(a[x], a[i]) && have >= min(y, a[i])){
            seg::add(0, n, i + 1, x, -1, 1);
            if(keep)
                ch[chpt++] = {i, x};
        }
        sum += a[i];
        i = seg::get_last(0, n, 0, i, sum + 1, 1);
    }
    a[x] = y;
    seg::upd(0, n, x, 1);
    return;
}
 
inline void undo(){
    for(int i = chpt - 1; i >= 0; i--){
        int l = ch[i].fi, r = ch[i].se;
        if(r == 0)
            continue;
        //cerr << "un done " << l << ' ' << r << '\n';
        if(r < 0){
            r *= -1;
            seg::add(0, n, l + 1, r, -1, 1);
        }
        else
            seg::add(0, n, l + 1, r, 1, 1);
    }
    chpt = 0;
}

inline void add(int l, int r){
    ll sum = seg::get_sum(0, n, l + 1, r, 1);
    if(sum >= min(a[l], a[r]))
        return;
    seg::add(0, n, l + 1, r, 1, 1);
}
 
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, false);
        else{
            ll keepx = a[x - 1], keepy = a[y + 1];
            chpt = 0;
            update(x - 1, inf, true);
            update(y + 1, inf, true);
            cout << seg::get_min(0, n, x, y + 1, 1).se << '\n';
            a[y + 1] = keepy;
            a[x - 1] = keepx;
            undo();
            seg::upd(0, n, x - 1, 1);
            seg::upd(0, n, y + 1, 1);
        }
    }
}
 
/*
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 

7
27 18 36 31 55 86 4 
4
1 7 18
1 7 60
1 3 11
2 1 6

7
27 18 36 31 55 86 60
3
2 2 3
1 3 11
2 1 6

8
41 53 10 12 43 91 11 92 
10
2 5 8
1 8 65
2 4 7
2 3 8
1 2 37
1 8 5
2 7 8
1 8 43
1 1 30
1 6 60
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 8 ms 408 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 9 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 8 ms 408 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 6 ms 412 KB Output is correct
16 Correct 7 ms 340 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 8 ms 408 KB Output is correct
19 Correct 4 ms 340 KB Output is correct
20 Correct 5 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 96 ms 8396 KB Output is correct
3 Correct 86 ms 8356 KB Output is correct
4 Correct 85 ms 8452 KB Output is correct
5 Correct 84 ms 8356 KB Output is correct
6 Correct 79 ms 8432 KB Output is correct
7 Correct 85 ms 8316 KB Output is correct
8 Correct 82 ms 8252 KB Output is correct
9 Correct 67 ms 8316 KB Output is correct
10 Correct 79 ms 8436 KB Output is correct
11 Correct 84 ms 8408 KB Output is correct
12 Correct 73 ms 8272 KB Output is correct
13 Correct 66 ms 8360 KB Output is correct
14 Correct 77 ms 8408 KB Output is correct
15 Correct 77 ms 8332 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 8 ms 408 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 9 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 8 ms 408 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 6 ms 412 KB Output is correct
16 Correct 7 ms 340 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 8 ms 408 KB Output is correct
19 Correct 4 ms 340 KB Output is correct
20 Correct 5 ms 348 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 96 ms 8396 KB Output is correct
23 Correct 86 ms 8356 KB Output is correct
24 Correct 85 ms 8452 KB Output is correct
25 Correct 84 ms 8356 KB Output is correct
26 Correct 79 ms 8432 KB Output is correct
27 Correct 85 ms 8316 KB Output is correct
28 Correct 82 ms 8252 KB Output is correct
29 Correct 67 ms 8316 KB Output is correct
30 Correct 79 ms 8436 KB Output is correct
31 Correct 84 ms 8408 KB Output is correct
32 Correct 73 ms 8272 KB Output is correct
33 Correct 66 ms 8360 KB Output is correct
34 Correct 77 ms 8408 KB Output is correct
35 Correct 77 ms 8332 KB Output is correct
36 Correct 120 ms 8896 KB Output is correct
37 Correct 123 ms 8652 KB Output is correct
38 Correct 110 ms 8760 KB Output is correct
39 Correct 100 ms 8896 KB Output is correct
40 Correct 114 ms 8736 KB Output is correct
41 Correct 95 ms 9288 KB Output is correct
42 Correct 90 ms 9256 KB Output is correct
43 Correct 102 ms 8440 KB Output is correct
44 Correct 110 ms 8496 KB Output is correct
45 Correct 129 ms 8940 KB Output is correct
46 Correct 116 ms 8888 KB Output is correct
47 Correct 103 ms 8716 KB Output is correct
48 Correct 88 ms 8560 KB Output is correct
49 Correct 97 ms 8596 KB Output is correct
50 Correct 97 ms 8888 KB Output is correct
51 Correct 96 ms 8780 KB Output is correct
52 Correct 101 ms 8780 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 96 ms 8396 KB Output is correct
3 Correct 86 ms 8356 KB Output is correct
4 Correct 85 ms 8452 KB Output is correct
5 Correct 84 ms 8356 KB Output is correct
6 Correct 79 ms 8432 KB Output is correct
7 Correct 85 ms 8316 KB Output is correct
8 Correct 82 ms 8252 KB Output is correct
9 Correct 67 ms 8316 KB Output is correct
10 Correct 79 ms 8436 KB Output is correct
11 Correct 84 ms 8408 KB Output is correct
12 Correct 73 ms 8272 KB Output is correct
13 Correct 66 ms 8360 KB Output is correct
14 Correct 77 ms 8408 KB Output is correct
15 Correct 77 ms 8332 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 3372 ms 9148 KB Output is correct
18 Correct 3435 ms 10936 KB Output is correct
19 Correct 3409 ms 10560 KB Output is correct
20 Execution timed out 4027 ms 10052 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 96 ms 8396 KB Output is correct
3 Correct 86 ms 8356 KB Output is correct
4 Correct 85 ms 8452 KB Output is correct
5 Correct 84 ms 8356 KB Output is correct
6 Correct 79 ms 8432 KB Output is correct
7 Correct 85 ms 8316 KB Output is correct
8 Correct 82 ms 8252 KB Output is correct
9 Correct 67 ms 8316 KB Output is correct
10 Correct 79 ms 8436 KB Output is correct
11 Correct 84 ms 8408 KB Output is correct
12 Correct 73 ms 8272 KB Output is correct
13 Correct 66 ms 8360 KB Output is correct
14 Correct 77 ms 8408 KB Output is correct
15 Correct 77 ms 8332 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1359 ms 8712 KB Output is correct
18 Correct 801 ms 10288 KB Output is correct
19 Correct 930 ms 9892 KB Output is correct
20 Correct 656 ms 10248 KB Output is correct
21 Correct 1268 ms 10064 KB Output is correct
22 Correct 787 ms 10348 KB Output is correct
23 Correct 1134 ms 9880 KB Output is correct
24 Correct 738 ms 10380 KB Output is correct
25 Correct 1004 ms 9920 KB Output is correct
26 Correct 406 ms 10992 KB Output is correct
27 Correct 441 ms 10796 KB Output is correct
28 Correct 543 ms 10128 KB Output is correct
29 Correct 407 ms 10888 KB Output is correct
30 Correct 456 ms 11036 KB Output is correct
31 Correct 625 ms 10108 KB Output is correct
32 Correct 749 ms 10556 KB Output is correct
33 Correct 379 ms 9832 KB Output is correct
34 Correct 686 ms 10592 KB Output is correct
35 Correct 327 ms 10312 KB Output is correct
36 Correct 630 ms 10312 KB Output is correct
37 Correct 399 ms 10048 KB Output is correct
38 Correct 319 ms 9932 KB Output is correct
39 Correct 439 ms 10468 KB Output is correct
40 Correct 267 ms 10580 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 8 ms 408 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 9 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 8 ms 408 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 6 ms 412 KB Output is correct
16 Correct 7 ms 340 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 8 ms 408 KB Output is correct
19 Correct 4 ms 340 KB Output is correct
20 Correct 5 ms 348 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 96 ms 8396 KB Output is correct
23 Correct 86 ms 8356 KB Output is correct
24 Correct 85 ms 8452 KB Output is correct
25 Correct 84 ms 8356 KB Output is correct
26 Correct 79 ms 8432 KB Output is correct
27 Correct 85 ms 8316 KB Output is correct
28 Correct 82 ms 8252 KB Output is correct
29 Correct 67 ms 8316 KB Output is correct
30 Correct 79 ms 8436 KB Output is correct
31 Correct 84 ms 8408 KB Output is correct
32 Correct 73 ms 8272 KB Output is correct
33 Correct 66 ms 8360 KB Output is correct
34 Correct 77 ms 8408 KB Output is correct
35 Correct 77 ms 8332 KB Output is correct
36 Correct 120 ms 8896 KB Output is correct
37 Correct 123 ms 8652 KB Output is correct
38 Correct 110 ms 8760 KB Output is correct
39 Correct 100 ms 8896 KB Output is correct
40 Correct 114 ms 8736 KB Output is correct
41 Correct 95 ms 9288 KB Output is correct
42 Correct 90 ms 9256 KB Output is correct
43 Correct 102 ms 8440 KB Output is correct
44 Correct 110 ms 8496 KB Output is correct
45 Correct 129 ms 8940 KB Output is correct
46 Correct 116 ms 8888 KB Output is correct
47 Correct 103 ms 8716 KB Output is correct
48 Correct 88 ms 8560 KB Output is correct
49 Correct 97 ms 8596 KB Output is correct
50 Correct 97 ms 8888 KB Output is correct
51 Correct 96 ms 8780 KB Output is correct
52 Correct 101 ms 8780 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 3372 ms 9148 KB Output is correct
55 Correct 3435 ms 10936 KB Output is correct
56 Correct 3409 ms 10560 KB Output is correct
57 Execution timed out 4027 ms 10052 KB Time limit exceeded
58 Halted 0 ms 0 KB -