oj.uz

Submission #730853

# Submission time Handle Problem Language Result Execution time Memory
730853 2023-04-26T14:26:41 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 9420 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, undopt = 0, lef[maxn5], rig[maxn5];
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 || lef[r] == l || rig[l] == r){
        if(a[l] <= a[r])
            rig[l] = r;
        if(a[r] <= a[l])
            lef[r] = l;
        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';
    if(a[l] <= a[r])
        rig[l] = r;
    if(a[r] <= a[l])
        lef[r] = l;
    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 << ' ' << lef[3] << '\n';
    if(l + 1 == r || (lef[r] != l && rig[l] != r))
        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';
    if(lef[r] == l)
        lef[r] = -1;
    if(rig[l] == r)
        rig[l] = -1;
    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(int sz){
    for(int i = undopt - 1; i >= sz; 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);
            if(lef[r] == l)
                lef[r] = -1;
            if(rig[l] == r)
                rig[l] = -1;
        }
        else{
            seg::add(0, n, l + 1, r, 1, 1);
            if(a[l] <= a[r])
                rig[l] = r;
            if(a[r] <= a[l])
                lef[r] = l;
        }
    }
    undopt = sz;
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    

    memset(lef, -1, sizeof lef);
    memset(rig, -1, sizeof rig);
 
    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);
            int keep = undopt;
            update(y + 1, inf, true);
            cout << seg::get_min(0, n, x, y + 1, 1).se << '\n';
            a[y + 1] = keepy;
            undo(keep);
            a[x - 1] = keepx;
            undo(0);
            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
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Incorrect 7 ms 1108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 57 ms 9000 KB Output is correct
3 Correct 53 ms 9036 KB Output is correct
4 Correct 56 ms 9076 KB Output is correct
5 Correct 55 ms 9084 KB Output is correct
6 Correct 62 ms 8944 KB Output is correct
7 Correct 50 ms 9036 KB Output is correct
8 Correct 49 ms 8896 KB Output is correct
9 Correct 42 ms 8964 KB Output is correct
10 Correct 50 ms 9036 KB Output is correct
11 Correct 45 ms 8996 KB Output is correct
12 Correct 44 ms 8928 KB Output is correct
13 Correct 44 ms 8952 KB Output is correct
14 Correct 50 ms 9064 KB Output is correct
15 Correct 52 ms 9016 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Incorrect 7 ms 1108 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 57 ms 9000 KB Output is correct
3 Correct 53 ms 9036 KB Output is correct
4 Correct 56 ms 9076 KB Output is correct
5 Correct 55 ms 9084 KB Output is correct
6 Correct 62 ms 8944 KB Output is correct
7 Correct 50 ms 9036 KB Output is correct
8 Correct 49 ms 8896 KB Output is correct
9 Correct 42 ms 8964 KB Output is correct
10 Correct 50 ms 9036 KB Output is correct
11 Correct 45 ms 8996 KB Output is correct
12 Correct 44 ms 8928 KB Output is correct
13 Correct 44 ms 8952 KB Output is correct
14 Correct 50 ms 9064 KB Output is correct
15 Correct 52 ms 9016 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Execution timed out 4035 ms 9420 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 57 ms 9000 KB Output is correct
3 Correct 53 ms 9036 KB Output is correct
4 Correct 56 ms 9076 KB Output is correct
5 Correct 55 ms 9084 KB Output is correct
6 Correct 62 ms 8944 KB Output is correct
7 Correct 50 ms 9036 KB Output is correct
8 Correct 49 ms 8896 KB Output is correct
9 Correct 42 ms 8964 KB Output is correct
10 Correct 50 ms 9036 KB Output is correct
11 Correct 45 ms 8996 KB Output is correct
12 Correct 44 ms 8928 KB Output is correct
13 Correct 44 ms 8952 KB Output is correct
14 Correct 50 ms 9064 KB Output is correct
15 Correct 52 ms 9016 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Incorrect 1410 ms 9228 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Incorrect 7 ms 1108 KB Output isn't correct
6 Halted 0 ms 0 KB -