Submission #590555

#	Time	Username	Problem	Language	Result	Execution time	Memory
590555		balbit	Fish 2 (JOI22_fish2)	C++14	8 / 100	104 ms	20812 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define pb push_back


#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x ){cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
int n,q;
int A[maxn];

namespace VS{ // value seg tree
    int mn[maxn*4], tg[maxn*4], cnt[maxn*4];
    inline void push(int o, int l, int r) {
        if (tg[o]) {
            mn[o] += tg[o];
            if (l != r) {
                tg[o*2] += tg[o];
                tg[o*2+1] += tg[o];
            }
            tg[o] = 0;
        }
    }
    void pull(int o) {
        mn[o] = min(mn[o*2], mn[o*2+1]);
        cnt[o] = 0;
        if (mn[o*2] == mn[o]) cnt[o] += cnt[o*2];
        if (mn[o*2+1] == mn[o]) cnt[o] += cnt[o*2+1];
    }
    void build(int o=1, int l=0, int r=maxn-1){
        if (l == r) {
            cnt[o] = 1;
            if (l < n) {
                mn[o] = 0;
            }else mn[o] = 1;
            return;
        }
        int mid = (l+r)/2;
        build(o*2,l,mid); build(o*2+1,mid+1,r);
        pull(o);
    }
    void MO(int L, int R, int v, int o=1, int l=0, int r=maxn-1) {
        push(o,l,r);
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            tg[o] += v; push(o,l,r); return;
        }
        int mid = (l+r)/2;
        MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r);
        pull(o);
    }
    int QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
        if (l > R || r < L) return 0;
        push(o,l,r);
        if (l >= L && r <= R) {
            return mn[o]<=2?cnt[o]:0;
        }
        int mid = (l+r)/2;
        return QU(L,R,o*2,l,mid) + QU(L,R,o*2+1,mid+1,r);
    }
};

namespace NXTS{ // next value seg tree
    int mx[maxn*4];

    void build(int o=1, int l=0, int r=maxn-1){
        if (l == r) {
            if (l < n) {
                mx[o] = A[l];
            }else{
                mx[o] = inf;
            }
            return;
        }
        int mid = (l+r)/2;
        build(o*2,l,mid); build(o*2+1,mid+1,r);
        mx[o] = max(mx[o*2], mx[o*2+1]);
    }
    void MO(int p, int v, int o=1, int l=0, int r=maxn-1) {
        if (l > p || r < p) return;
        if (l == r) {
            mx[o] = v; return;
        }
        int mid = (l+r)/2;
        MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
        mx[o] = max(mx[o*2], mx[o*2+1]);
    }
    int Qright(int L, int R, int v, int o=1, int l=0, int r=maxn-1) { // rightmost point in this range geq than v
        if (mx[o] < v || l > R || r < L) return -1;
        if (l == r) return l;
        int mid = (l+r)/2;
        int gr = Qright(L,R,v,o*2+1,mid+1,r);
        if (gr == -1) return Qright(L,R,v,o*2,l,mid);
        else return gr;
    }
    int Qleft(int L, int R, int v, int o=1, int l=0, int r=maxn-1) { // rightmost point in this range geq than v
        if (mx[o] < v || l > R || r < L) return -1;
        if (l == r) return l;
        int mid = (l+r)/2;
        int gl = Qleft(L,R,v,o*2,l,mid);
        if (gl == -1) return Qleft(L,R,v,o*2+1,mid+1,r);
        else return gl;
    }
};

namespace BIT{
    // for range sum only i guess
    ll s[maxn];
    ll QU(int e) {
        ll re = 0; for (++e; e>0; e-=e&-e) re += s[e]; return re;
    }
    ll QU(int l, int r) {
        return QU(r) - QU(l-1);
    }
    void MO(int e, int v) {
        for (++e; e<maxn; e+=e&-e) {
            s[e] += v;
        }
    }
}

int toL[maxn], toR[maxn];

vector<int> fromL[maxn], fromR[maxn]; // from my left, from my right



void updl(int v) {
    if (toL[v]!=-1) {
        int p = toL[v];
        toL[v] = -1;
        VS::MO(p+1, v-1, -1);
        fromR[p].erase(find(ALL(fromR[p]), v));
    }
    int P = NXTS::Qright(0,v-1,A[v]);
//    bug(v,P);
    if (P != -1 && P != v-1) {
        assert(A[P] >= A[v]);
        ll btw = BIT::QU(P+1, v-1);
        if (btw < A[v]) {
            // yay
            fromR[P].pb(v);
            VS::MO(P+1, v-1, 1);
            toL[v] = P;
            bug(v, P);
        }
    }
}

void updr(int v) {
    if (toR[v]!=-1) {
        int p = toR[v];
        toR[v] = -1;
        VS::MO(v+1,p-1, -1);
        fromL[p].erase(find(ALL(fromL[p]), v));
    }
    int P = NXTS::Qleft(v+1,n-1,A[v]);
//    bug(v,P);
    if (P != -1 && P != v-1) {
        assert(A[P] >= A[v]);
        ll btw = BIT::QU(v+1,P-1);
        if (btw < A[v]) {
            fromL[P].pb(v);
            VS::MO(v+1, P-1, 1);
            toR[v] = P;
            bug(v, P);
        }
    }
}



signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    cin>>n;
    n+=2;
    REP1(i,n-2) {
        cin>>A[i];
    }
    A[0] = A[n-1] = 1e15+10;
    REP(i,n){
        BIT::MO(i, A[i]);
    }
    VS::build(); NXTS::build();

    memset(toL, -1, sizeof toL);
    memset(toR, -1, sizeof toR);

    REP(i,n) {
        updl(i); updr(i);
    }

    cin>>q;

    while (q--) {
        int tp, l, r; cin>>tp>>l>>r;
        int gt = VS::QU(l,r);
        cout<<gt<<endl;
    }


}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17