Submission #730371

#	Time	Username	Problem	Language	Result	Execution time	Memory
730371		fatemetmhr	Fish 2 (JOI22_fish2)	C++17	60 / 100	4026 ms	12804 KiB

fish2

// ~ 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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 17