oj.uz

Submission #730830

# Submission time Handle Problem Language Result Execution time Memory
730830 2023-04-26T13:42:33 Z fatemetmhr Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 11256 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(){
    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);
            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 = 0;
}
 
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);
            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
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 1124 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 63 ms 9648 KB Output is correct
3 Correct 56 ms 9400 KB Output is correct
4 Correct 62 ms 9624 KB Output is correct
5 Correct 57 ms 9348 KB Output is correct
6 Correct 51 ms 9864 KB Output is correct
7 Correct 42 ms 9264 KB Output is correct
8 Correct 51 ms 9932 KB Output is correct
9 Correct 42 ms 9288 KB Output is correct
10 Correct 51 ms 9664 KB Output is correct
11 Correct 48 ms 9300 KB Output is correct
12 Correct 51 ms 9224 KB Output is correct
13 Correct 46 ms 9208 KB Output is correct
14 Correct 53 ms 9576 KB Output is correct
15 Correct 58 ms 9580 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 1124 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 63 ms 9648 KB Output is correct
3 Correct 56 ms 9400 KB Output is correct
4 Correct 62 ms 9624 KB Output is correct
5 Correct 57 ms 9348 KB Output is correct
6 Correct 51 ms 9864 KB Output is correct
7 Correct 42 ms 9264 KB Output is correct
8 Correct 51 ms 9932 KB Output is correct
9 Correct 42 ms 9288 KB Output is correct
10 Correct 51 ms 9664 KB Output is correct
11 Correct 48 ms 9300 KB Output is correct
12 Correct 51 ms 9224 KB Output is correct
13 Correct 46 ms 9208 KB Output is correct
14 Correct 53 ms 9576 KB Output is correct
15 Correct 58 ms 9580 KB Output is correct
16 Correct 1 ms 1124 KB Output is correct
17 Execution timed out 4043 ms 11256 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 63 ms 9648 KB Output is correct
3 Correct 56 ms 9400 KB Output is correct
4 Correct 62 ms 9624 KB Output is correct
5 Correct 57 ms 9348 KB Output is correct
6 Correct 51 ms 9864 KB Output is correct
7 Correct 42 ms 9264 KB Output is correct
8 Correct 51 ms 9932 KB Output is correct
9 Correct 42 ms 9288 KB Output is correct
10 Correct 51 ms 9664 KB Output is correct
11 Correct 48 ms 9300 KB Output is correct
12 Correct 51 ms 9224 KB Output is correct
13 Correct 46 ms 9208 KB Output is correct
14 Correct 53 ms 9576 KB Output is correct
15 Correct 58 ms 9580 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Incorrect 1381 ms 10624 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 1124 KB Output is correct
5 Incorrect 7 ms 1108 KB Output isn't correct
6 Halted 0 ms 0 KB -