oj.uz

Submission #730380

# Submission time Handle Problem Language Result Execution time Memory
730380 2023-04-25T18:46:48 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 12872 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 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 11 ms 420 KB Output is correct
6 Correct 15 ms 424 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 22 ms 420 KB Output is correct
9 Correct 14 ms 416 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 7 ms 416 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 12 ms 412 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 9 ms 420 KB Output is correct
16 Correct 9 ms 408 KB Output is correct
17 Correct 5 ms 340 KB Output is correct
18 Correct 9 ms 340 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 7 ms 340 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 99 ms 12252 KB Output is correct
3 Correct 77 ms 11856 KB Output is correct
4 Correct 97 ms 12264 KB Output is correct
5 Correct 76 ms 11792 KB Output is correct
6 Correct 63 ms 10252 KB Output is correct
7 Correct 63 ms 9412 KB Output is correct
8 Correct 67 ms 10252 KB Output is correct
9 Correct 50 ms 9500 KB Output is correct
10 Correct 64 ms 10056 KB Output is correct
11 Correct 59 ms 10060 KB Output is correct
12 Correct 66 ms 10028 KB Output is correct
13 Correct 63 ms 9976 KB Output is correct
14 Correct 76 ms 11552 KB Output is correct
15 Correct 75 ms 11340 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 11 ms 420 KB Output is correct
6 Correct 15 ms 424 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 22 ms 420 KB Output is correct
9 Correct 14 ms 416 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 7 ms 416 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 12 ms 412 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 9 ms 420 KB Output is correct
16 Correct 9 ms 408 KB Output is correct
17 Correct 5 ms 340 KB Output is correct
18 Correct 9 ms 340 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 7 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 99 ms 12252 KB Output is correct
23 Correct 77 ms 11856 KB Output is correct
24 Correct 97 ms 12264 KB Output is correct
25 Correct 76 ms 11792 KB Output is correct
26 Correct 63 ms 10252 KB Output is correct
27 Correct 63 ms 9412 KB Output is correct
28 Correct 67 ms 10252 KB Output is correct
29 Correct 50 ms 9500 KB Output is correct
30 Correct 64 ms 10056 KB Output is correct
31 Correct 59 ms 10060 KB Output is correct
32 Correct 66 ms 10028 KB Output is correct
33 Correct 63 ms 9976 KB Output is correct
34 Correct 76 ms 11552 KB Output is correct
35 Correct 75 ms 11340 KB Output is correct
36 Correct 157 ms 12748 KB Output is correct
37 Correct 130 ms 11932 KB Output is correct
38 Correct 135 ms 11464 KB Output is correct
39 Correct 151 ms 12872 KB Output is correct
40 Correct 153 ms 11396 KB Output is correct
41 Correct 85 ms 10364 KB Output is correct
42 Correct 86 ms 10392 KB Output is correct
43 Correct 110 ms 9548 KB Output is correct
44 Correct 121 ms 9500 KB Output is correct
45 Correct 131 ms 10444 KB Output is correct
46 Correct 108 ms 10228 KB Output is correct
47 Correct 109 ms 9180 KB Output is correct
48 Correct 79 ms 10144 KB Output is correct
49 Correct 90 ms 10060 KB Output is correct
50 Correct 92 ms 11412 KB Output is correct
51 Correct 93 ms 11304 KB Output is correct
52 Correct 97 ms 11464 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 99 ms 12252 KB Output is correct
3 Correct 77 ms 11856 KB Output is correct
4 Correct 97 ms 12264 KB Output is correct
5 Correct 76 ms 11792 KB Output is correct
6 Correct 63 ms 10252 KB Output is correct
7 Correct 63 ms 9412 KB Output is correct
8 Correct 67 ms 10252 KB Output is correct
9 Correct 50 ms 9500 KB Output is correct
10 Correct 64 ms 10056 KB Output is correct
11 Correct 59 ms 10060 KB Output is correct
12 Correct 66 ms 10028 KB Output is correct
13 Correct 63 ms 9976 KB Output is correct
14 Correct 76 ms 11552 KB Output is correct
15 Correct 75 ms 11340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4078 ms 12120 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 99 ms 12252 KB Output is correct
3 Correct 77 ms 11856 KB Output is correct
4 Correct 97 ms 12264 KB Output is correct
5 Correct 76 ms 11792 KB Output is correct
6 Correct 63 ms 10252 KB Output is correct
7 Correct 63 ms 9412 KB Output is correct
8 Correct 67 ms 10252 KB Output is correct
9 Correct 50 ms 9500 KB Output is correct
10 Correct 64 ms 10056 KB Output is correct
11 Correct 59 ms 10060 KB Output is correct
12 Correct 66 ms 10028 KB Output is correct
13 Correct 63 ms 9976 KB Output is correct
14 Correct 76 ms 11552 KB Output is correct
15 Correct 75 ms 11340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1908 ms 12500 KB Output is correct
18 Correct 1226 ms 12596 KB Output is correct
19 Correct 1196 ms 12332 KB Output is correct
20 Correct 953 ms 12604 KB Output is correct
21 Correct 1705 ms 12488 KB Output is correct
22 Correct 1198 ms 12636 KB Output is correct
23 Correct 1514 ms 12328 KB Output is correct
24 Correct 1120 ms 12548 KB Output is correct
25 Correct 1362 ms 12100 KB Output is correct
26 Correct 459 ms 10668 KB Output is correct
27 Correct 618 ms 10348 KB Output is correct
28 Correct 765 ms 11408 KB Output is correct
29 Correct 516 ms 10596 KB Output is correct
30 Correct 618 ms 10360 KB Output is correct
31 Correct 907 ms 11400 KB Output is correct
32 Correct 1102 ms 11596 KB Output is correct
33 Correct 397 ms 10220 KB Output is correct
34 Correct 1069 ms 12420 KB Output is correct
35 Correct 367 ms 10276 KB Output is correct
36 Correct 974 ms 11572 KB Output is correct
37 Correct 563 ms 11332 KB Output is correct
38 Correct 384 ms 11184 KB Output is correct
39 Correct 596 ms 11916 KB Output is correct
40 Correct 306 ms 11816 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 11 ms 420 KB Output is correct
6 Correct 15 ms 424 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 22 ms 420 KB Output is correct
9 Correct 14 ms 416 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 7 ms 416 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 12 ms 412 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 9 ms 420 KB Output is correct
16 Correct 9 ms 408 KB Output is correct
17 Correct 5 ms 340 KB Output is correct
18 Correct 9 ms 340 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 7 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 99 ms 12252 KB Output is correct
23 Correct 77 ms 11856 KB Output is correct
24 Correct 97 ms 12264 KB Output is correct
25 Correct 76 ms 11792 KB Output is correct
26 Correct 63 ms 10252 KB Output is correct
27 Correct 63 ms 9412 KB Output is correct
28 Correct 67 ms 10252 KB Output is correct
29 Correct 50 ms 9500 KB Output is correct
30 Correct 64 ms 10056 KB Output is correct
31 Correct 59 ms 10060 KB Output is correct
32 Correct 66 ms 10028 KB Output is correct
33 Correct 63 ms 9976 KB Output is correct
34 Correct 76 ms 11552 KB Output is correct
35 Correct 75 ms 11340 KB Output is correct
36 Correct 157 ms 12748 KB Output is correct
37 Correct 130 ms 11932 KB Output is correct
38 Correct 135 ms 11464 KB Output is correct
39 Correct 151 ms 12872 KB Output is correct
40 Correct 153 ms 11396 KB Output is correct
41 Correct 85 ms 10364 KB Output is correct
42 Correct 86 ms 10392 KB Output is correct
43 Correct 110 ms 9548 KB Output is correct
44 Correct 121 ms 9500 KB Output is correct
45 Correct 131 ms 10444 KB Output is correct
46 Correct 108 ms 10228 KB Output is correct
47 Correct 109 ms 9180 KB Output is correct
48 Correct 79 ms 10144 KB Output is correct
49 Correct 90 ms 10060 KB Output is correct
50 Correct 92 ms 11412 KB Output is correct
51 Correct 93 ms 11304 KB Output is correct
52 Correct 97 ms 11464 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4078 ms 12120 KB Time limit exceeded
55 Halted 0 ms 0 KB -