oj.uz

Submission #985770

# Submission time Handle Problem Language Result Execution time Memory
985770 2024-05-18T17:21:05 Z GrindMachine Fish 2 (JOI22_fish2) C++17
31 / 100
 527 ms 25996 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/101003?#comment-898608

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        ll mn,cnt;
    };

    struct lazy {
        ll a;
    };

    data d_neutral = {inf2,0};
    lazy l_neutral = {0};

    void merge(data &curr, data &left, data &right) {
        curr.mn = min(left.mn,right.mn);
        curr.cnt = 0;
        if(left.mn == curr.mn) curr.cnt += left.cnt;
        if(right.mn == curr.mn) curr.cnt += right.cnt;
    }

    void create(int x, int lx, int rx, T v) {
        tr[x] = {v,1};
    }

    void modify(int x, int lx, int rx, T v) {
        lz[x].a = v;
    }

    void propagate(int x, int lx, int rx) {
        ll v = lz[x].a;
        if(!v) return;

        tr[x].mn += v;

        if(rx-lx > 1){
            lz[2*x+1].a += v;
            lz[2*x+2].a += v;
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree() {

    }

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, 0);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(n, 2 * x + 1, lx, mid);
        build(n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(int n) {
        build(n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }
};

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll sum,mnp,mns,val1,val2;
    };

    data neutral = {0,0,0,inf2,inf2};

    data merge(data &left, data &right) {
        data curr;

        curr.sum = left.sum+right.sum;
        curr.mnp = min({left.mnp,left.sum+right.mnp});
        curr.mns = min({right.mns,right.sum+left.mns});
        curr.val1 = min({left.val1,curr.mnp});
        curr.val2 = min({right.val2,curr.mns});

        return curr;
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {
        tr[i] = {v,-v,-v};
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];
    a[0] = a[n+1] = inf2;
    vector<ll> p(n+5);
    rep1(i,n) p[i] = p[i-1]+a[i];

    vector<ll> ngel(n+5), nger(n+5,n+1);

    {
        stack<ll> stk;

        rep1(i,n){
            while(!stk.empty() and a[i] >= a[stk.top()]){
                nger[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
    }

    {
        stack<ll> stk;

        rev(i,n,1){
            while(!stk.empty() and a[i] >= a[stk.top()]){
                ngel[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
    }

    set<pll> pairs;

    auto add_pair = [&](ll l, ll r){
        if(l > r) swap(l,r);
        if(r-l-1 <= 0) return;

        ll sum = p[r-1]-p[l];
        if(min(a[l],a[r]) > sum){
            pairs.insert({l+1,r-1});
        }
    };

    rep1(i,n){
        add_pair(i,ngel[i]);
        add_pair(i,nger[i]);
    }

    lazysegtree<ll> st(n+5);
    st.build(n+1);
    for(auto [l,r] : pairs){
        st.rupd(l,r,1);
    }

    segtree<ll> seg(n+5);
    rep1(i,n) seg.pupd(i,a[i]);

    ll q; cin >> q;
    while(q--){
        ll t,l,r; cin >> t >> l >> r;
        ll pos1 = l, pos2 = r;

        {
            ll lo = l, hi = r;
            while(lo <= hi){
                ll mid = (lo+hi) >> 1;
                if(p[mid-1]-p[l-1]+seg.query(mid,r).val1 < 0){
                    pos1 = mid;
                    lo = mid+1;
                }
                else{
                    hi = mid-1;
                }
            }
        }

        {
            ll lo = l, hi = r;
            while(lo <= hi){
                ll mid = (lo+hi) >> 1;
                if(p[r]-p[mid]+seg.query(l,mid).val2 < 0){
                    pos2 = mid;
                    hi = mid-1;
                }
                else{
                    lo = mid+1;
                }
            }
        }

        ll ans = st.query(pos1,pos2).cnt;
        cout << ans << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 65 ms 22832 KB Output is correct
3 Correct 52 ms 22344 KB Output is correct
4 Correct 57 ms 22868 KB Output is correct
5 Correct 56 ms 22216 KB Output is correct
6 Correct 39 ms 20180 KB Output is correct
7 Correct 36 ms 19036 KB Output is correct
8 Correct 49 ms 20312 KB Output is correct
9 Correct 35 ms 19372 KB Output is correct
10 Correct 43 ms 20560 KB Output is correct
11 Correct 39 ms 20040 KB Output is correct
12 Correct 38 ms 20060 KB Output is correct
13 Correct 34 ms 20048 KB Output is correct
14 Correct 45 ms 22280 KB Output is correct
15 Correct 46 ms 22160 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 65 ms 22832 KB Output is correct
3 Correct 52 ms 22344 KB Output is correct
4 Correct 57 ms 22868 KB Output is correct
5 Correct 56 ms 22216 KB Output is correct
6 Correct 39 ms 20180 KB Output is correct
7 Correct 36 ms 19036 KB Output is correct
8 Correct 49 ms 20312 KB Output is correct
9 Correct 35 ms 19372 KB Output is correct
10 Correct 43 ms 20560 KB Output is correct
11 Correct 39 ms 20040 KB Output is correct
12 Correct 38 ms 20060 KB Output is correct
13 Correct 34 ms 20048 KB Output is correct
14 Correct 45 ms 22280 KB Output is correct
15 Correct 46 ms 22160 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 478 ms 24400 KB Output is correct
18 Correct 506 ms 25788 KB Output is correct
19 Correct 461 ms 24468 KB Output is correct
20 Correct 479 ms 24548 KB Output is correct
21 Correct 471 ms 24324 KB Output is correct
22 Correct 527 ms 25996 KB Output is correct
23 Correct 439 ms 24404 KB Output is correct
24 Correct 495 ms 24572 KB Output is correct
25 Correct 444 ms 24692 KB Output is correct
26 Correct 456 ms 24736 KB Output is correct
27 Correct 468 ms 22976 KB Output is correct
28 Correct 459 ms 23072 KB Output is correct
29 Correct 438 ms 23040 KB Output is correct
30 Correct 390 ms 20856 KB Output is correct
31 Correct 373 ms 20720 KB Output is correct
32 Correct 434 ms 21796 KB Output is correct
33 Correct 453 ms 22248 KB Output is correct
34 Correct 412 ms 21456 KB Output is correct
35 Correct 427 ms 20988 KB Output is correct
36 Correct 487 ms 22900 KB Output is correct
37 Correct 383 ms 21872 KB Output is correct
38 Correct 329 ms 22136 KB Output is correct
39 Correct 451 ms 24148 KB Output is correct
40 Correct 518 ms 24152 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 65 ms 22832 KB Output is correct
3 Correct 52 ms 22344 KB Output is correct
4 Correct 57 ms 22868 KB Output is correct
5 Correct 56 ms 22216 KB Output is correct
6 Correct 39 ms 20180 KB Output is correct
7 Correct 36 ms 19036 KB Output is correct
8 Correct 49 ms 20312 KB Output is correct
9 Correct 35 ms 19372 KB Output is correct
10 Correct 43 ms 20560 KB Output is correct
11 Correct 39 ms 20040 KB Output is correct
12 Correct 38 ms 20060 KB Output is correct
13 Correct 34 ms 20048 KB Output is correct
14 Correct 45 ms 22280 KB Output is correct
15 Correct 46 ms 22160 KB Output is correct
16 Runtime error 1 ms 604 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -