oj.uz

Submission #730834

# Submission time Handle Problem Language Result Execution time Memory
730834 2023-04-26T13:47:37 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)
        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 << '\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;
        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 
*/

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 6 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 60 ms 8992 KB Output is correct
3 Correct 58 ms 9036 KB Output is correct
4 Correct 59 ms 9036 KB Output is correct
5 Correct 57 ms 9020 KB Output is correct
6 Correct 50 ms 8964 KB Output is correct
7 Correct 50 ms 9044 KB Output is correct
8 Correct 51 ms 8992 KB Output is correct
9 Correct 54 ms 9060 KB Output is correct
10 Correct 47 ms 8968 KB Output is correct
11 Correct 48 ms 9080 KB Output is correct
12 Correct 45 ms 8948 KB Output is correct
13 Correct 47 ms 8972 KB Output is correct
14 Correct 53 ms 9000 KB Output is correct
15 Correct 51 ms 9036 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 6 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 60 ms 8992 KB Output is correct
3 Correct 58 ms 9036 KB Output is correct
4 Correct 59 ms 9036 KB Output is correct
5 Correct 57 ms 9020 KB Output is correct
6 Correct 50 ms 8964 KB Output is correct
7 Correct 50 ms 9044 KB Output is correct
8 Correct 51 ms 8992 KB Output is correct
9 Correct 54 ms 9060 KB Output is correct
10 Correct 47 ms 8968 KB Output is correct
11 Correct 48 ms 9080 KB Output is correct
12 Correct 45 ms 8948 KB Output is correct
13 Correct 47 ms 8972 KB Output is correct
14 Correct 53 ms 9000 KB Output is correct
15 Correct 51 ms 9036 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Execution timed out 4070 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 60 ms 8992 KB Output is correct
3 Correct 58 ms 9036 KB Output is correct
4 Correct 59 ms 9036 KB Output is correct
5 Correct 57 ms 9020 KB Output is correct
6 Correct 50 ms 8964 KB Output is correct
7 Correct 50 ms 9044 KB Output is correct
8 Correct 51 ms 8992 KB Output is correct
9 Correct 54 ms 9060 KB Output is correct
10 Correct 47 ms 8968 KB Output is correct
11 Correct 48 ms 9080 KB Output is correct
12 Correct 45 ms 8948 KB Output is correct
13 Correct 47 ms 8972 KB Output is correct
14 Correct 53 ms 9000 KB Output is correct
15 Correct 51 ms 9036 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Incorrect 1420 ms 9268 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 6 ms 1108 KB Output isn't correct
6 Halted 0 ms 0 KB -