oj.uz

Submission #590555

# Submission time Handle Problem Language Result Execution time Memory
590555 2022-07-06T06:30:10 Z balbit Fish 2 (JOI22_fish2) C++14
8 / 100
 104 ms 20812 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12708 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 8 ms 12708 KB Output is correct
2 Correct 93 ms 20804 KB Output is correct
3 Correct 104 ms 20428 KB Output is correct
4 Correct 95 ms 20812 KB Output is correct
5 Correct 94 ms 20440 KB Output is correct
6 Correct 84 ms 19552 KB Output is correct
7 Correct 67 ms 19020 KB Output is correct
8 Correct 91 ms 19460 KB Output is correct
9 Correct 67 ms 18952 KB Output is correct
10 Correct 88 ms 19644 KB Output is correct
11 Correct 96 ms 19720 KB Output is correct
12 Correct 69 ms 18808 KB Output is correct
13 Correct 67 ms 18860 KB Output is correct
14 Correct 78 ms 19476 KB Output is correct
15 Correct 79 ms 19544 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12708 KB Output is correct
2 Correct 93 ms 20804 KB Output is correct
3 Correct 104 ms 20428 KB Output is correct
4 Correct 95 ms 20812 KB Output is correct
5 Correct 94 ms 20440 KB Output is correct
6 Correct 84 ms 19552 KB Output is correct
7 Correct 67 ms 19020 KB Output is correct
8 Correct 91 ms 19460 KB Output is correct
9 Correct 67 ms 18952 KB Output is correct
10 Correct 88 ms 19644 KB Output is correct
11 Correct 96 ms 19720 KB Output is correct
12 Correct 69 ms 18808 KB Output is correct
13 Correct 67 ms 18860 KB Output is correct
14 Correct 78 ms 19476 KB Output is correct
15 Correct 79 ms 19544 KB Output is correct
16 Incorrect 8 ms 12756 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12708 KB Output is correct
2 Correct 93 ms 20804 KB Output is correct
3 Correct 104 ms 20428 KB Output is correct
4 Correct 95 ms 20812 KB Output is correct
5 Correct 94 ms 20440 KB Output is correct
6 Correct 84 ms 19552 KB Output is correct
7 Correct 67 ms 19020 KB Output is correct
8 Correct 91 ms 19460 KB Output is correct
9 Correct 67 ms 18952 KB Output is correct
10 Correct 88 ms 19644 KB Output is correct
11 Correct 96 ms 19720 KB Output is correct
12 Correct 69 ms 18808 KB Output is correct
13 Correct 67 ms 18860 KB Output is correct
14 Correct 78 ms 19476 KB Output is correct
15 Correct 79 ms 19544 KB Output is correct
16 Incorrect 7 ms 12756 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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