oj.uz

Submission #730917

# Submission time Handle Problem Language Result Execution time Memory
730917 2023-04-26T15:40:17 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 8288 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   =  1e17;
 
 
ll a[maxn5];
int n, chpt = 0;
pii ch[maxn];
vector <ll> av;

namespace fen{

    ll fen[maxn5];

    inline void add(int id, ll val){
        for(++id; id < maxn5; id += id & -id)
            fen[id] += val;
    }

    inline ll get(int id){
        ll ret = 0;
        for(++id; id; id -= id & -id)
            ret += fen[id];
        return ret;
    }

    inline ll get(int l, int r){
        if(r < l)
            return 0;
        if(l == r)
            return a[l];
        return get(r) - (l ? get(l - 1) : 0);
    }
}
 
namespace seg{
 
    pii mn[maxnt];
    int lazy[maxnt];
    ll 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] = 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]);
    }
 
    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];
    }
 
    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 = fen::get(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 = fen::get(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 = fen::get(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);
        }
        fen::add(x, y - a[x]);
        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 = fen::get(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 = fen::get(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 = fen::get(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);
    }
    fen::add(x, y - a[x]);
    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 = fen::get(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);
    fen::add(0, inf);
    for(int i = 1; i < n; i++){
        if(i < n - 1)
            cin >> a[i];
        seg::upd(0, n, i, 1);
        fen::add(i, a[i]);
        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();
            fen::add(x - 1, keepx - inf);
            fen::add(y + 1, keepy - inf);
            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 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 5 ms 424 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 11 ms 340 KB Output is correct
9 Correct 7 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 7 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 6 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 4 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 63 ms 7344 KB Output is correct
3 Correct 67 ms 7344 KB Output is correct
4 Correct 71 ms 7380 KB Output is correct
5 Correct 79 ms 7376 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 43 ms 7200 KB Output is correct
8 Correct 56 ms 7288 KB Output is correct
9 Correct 48 ms 7176 KB Output is correct
10 Correct 58 ms 7328 KB Output is correct
11 Correct 52 ms 7304 KB Output is correct
12 Correct 49 ms 7172 KB Output is correct
13 Correct 49 ms 7132 KB Output is correct
14 Correct 69 ms 7340 KB Output is correct
15 Correct 65 ms 7288 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 5 ms 424 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 11 ms 340 KB Output is correct
9 Correct 7 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 7 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 6 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 63 ms 7344 KB Output is correct
23 Correct 67 ms 7344 KB Output is correct
24 Correct 71 ms 7380 KB Output is correct
25 Correct 79 ms 7376 KB Output is correct
26 Correct 55 ms 7196 KB Output is correct
27 Correct 43 ms 7200 KB Output is correct
28 Correct 56 ms 7288 KB Output is correct
29 Correct 48 ms 7176 KB Output is correct
30 Correct 58 ms 7328 KB Output is correct
31 Correct 52 ms 7304 KB Output is correct
32 Correct 49 ms 7172 KB Output is correct
33 Correct 49 ms 7132 KB Output is correct
34 Correct 69 ms 7340 KB Output is correct
35 Correct 65 ms 7288 KB Output is correct
36 Correct 87 ms 7580 KB Output is correct
37 Correct 87 ms 7388 KB Output is correct
38 Correct 86 ms 7352 KB Output is correct
39 Correct 84 ms 7524 KB Output is correct
40 Correct 85 ms 7292 KB Output is correct
41 Correct 66 ms 7752 KB Output is correct
42 Correct 65 ms 7724 KB Output is correct
43 Correct 70 ms 7136 KB Output is correct
44 Correct 78 ms 7164 KB Output is correct
45 Correct 95 ms 7612 KB Output is correct
46 Correct 78 ms 7504 KB Output is correct
47 Correct 80 ms 7324 KB Output is correct
48 Correct 57 ms 7296 KB Output is correct
49 Correct 62 ms 7296 KB Output is correct
50 Correct 65 ms 7628 KB Output is correct
51 Correct 71 ms 7624 KB Output is correct
52 Correct 75 ms 7564 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 63 ms 7344 KB Output is correct
3 Correct 67 ms 7344 KB Output is correct
4 Correct 71 ms 7380 KB Output is correct
5 Correct 79 ms 7376 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 43 ms 7200 KB Output is correct
8 Correct 56 ms 7288 KB Output is correct
9 Correct 48 ms 7176 KB Output is correct
10 Correct 58 ms 7328 KB Output is correct
11 Correct 52 ms 7304 KB Output is correct
12 Correct 49 ms 7172 KB Output is correct
13 Correct 49 ms 7132 KB Output is correct
14 Correct 69 ms 7340 KB Output is correct
15 Correct 65 ms 7288 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2679 ms 7988 KB Output is correct
18 Correct 2909 ms 8216 KB Output is correct
19 Correct 2663 ms 8288 KB Output is correct
20 Execution timed out 4049 ms 8204 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 328 KB Output is correct
2 Correct 63 ms 7344 KB Output is correct
3 Correct 67 ms 7344 KB Output is correct
4 Correct 71 ms 7380 KB Output is correct
5 Correct 79 ms 7376 KB Output is correct
6 Correct 55 ms 7196 KB Output is correct
7 Correct 43 ms 7200 KB Output is correct
8 Correct 56 ms 7288 KB Output is correct
9 Correct 48 ms 7176 KB Output is correct
10 Correct 58 ms 7328 KB Output is correct
11 Correct 52 ms 7304 KB Output is correct
12 Correct 49 ms 7172 KB Output is correct
13 Correct 49 ms 7132 KB Output is correct
14 Correct 69 ms 7340 KB Output is correct
15 Correct 65 ms 7288 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 796 ms 7436 KB Output is correct
18 Correct 512 ms 7960 KB Output is correct
19 Correct 546 ms 8012 KB Output is correct
20 Correct 456 ms 7992 KB Output is correct
21 Correct 711 ms 7852 KB Output is correct
22 Correct 520 ms 7932 KB Output is correct
23 Correct 656 ms 7948 KB Output is correct
24 Correct 525 ms 7844 KB Output is correct
25 Correct 570 ms 7892 KB Output is correct
26 Correct 235 ms 7868 KB Output is correct
27 Correct 323 ms 7748 KB Output is correct
28 Correct 347 ms 8028 KB Output is correct
29 Correct 333 ms 7836 KB Output is correct
30 Correct 287 ms 7672 KB Output is correct
31 Correct 397 ms 7892 KB Output is correct
32 Correct 514 ms 7856 KB Output is correct
33 Correct 188 ms 7880 KB Output is correct
34 Correct 481 ms 7920 KB Output is correct
35 Correct 185 ms 7944 KB Output is correct
36 Correct 481 ms 7988 KB Output is correct
37 Correct 288 ms 8024 KB Output is correct
38 Correct 268 ms 8080 KB Output is correct
39 Correct 286 ms 8020 KB Output is correct
40 Correct 189 ms 8272 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 5 ms 424 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 11 ms 340 KB Output is correct
9 Correct 7 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 3 ms 344 KB Output is correct
13 Correct 7 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 6 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 4 ms 340 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 63 ms 7344 KB Output is correct
23 Correct 67 ms 7344 KB Output is correct
24 Correct 71 ms 7380 KB Output is correct
25 Correct 79 ms 7376 KB Output is correct
26 Correct 55 ms 7196 KB Output is correct
27 Correct 43 ms 7200 KB Output is correct
28 Correct 56 ms 7288 KB Output is correct
29 Correct 48 ms 7176 KB Output is correct
30 Correct 58 ms 7328 KB Output is correct
31 Correct 52 ms 7304 KB Output is correct
32 Correct 49 ms 7172 KB Output is correct
33 Correct 49 ms 7132 KB Output is correct
34 Correct 69 ms 7340 KB Output is correct
35 Correct 65 ms 7288 KB Output is correct
36 Correct 87 ms 7580 KB Output is correct
37 Correct 87 ms 7388 KB Output is correct
38 Correct 86 ms 7352 KB Output is correct
39 Correct 84 ms 7524 KB Output is correct
40 Correct 85 ms 7292 KB Output is correct
41 Correct 66 ms 7752 KB Output is correct
42 Correct 65 ms 7724 KB Output is correct
43 Correct 70 ms 7136 KB Output is correct
44 Correct 78 ms 7164 KB Output is correct
45 Correct 95 ms 7612 KB Output is correct
46 Correct 78 ms 7504 KB Output is correct
47 Correct 80 ms 7324 KB Output is correct
48 Correct 57 ms 7296 KB Output is correct
49 Correct 62 ms 7296 KB Output is correct
50 Correct 65 ms 7628 KB Output is correct
51 Correct 71 ms 7624 KB Output is correct
52 Correct 75 ms 7564 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 2679 ms 7988 KB Output is correct
55 Correct 2909 ms 8216 KB Output is correct
56 Correct 2663 ms 8288 KB Output is correct
57 Execution timed out 4049 ms 8204 KB Time limit exceeded
58 Halted 0 ms 0 KB -