oj.uz

Submission #590585

# Submission time Handle Problem Language Result Execution time Memory
590585 2022-07-06T07:03:50 Z balbit Fish 2 (JOI22_fish2) C++14
43 / 100
 1480 ms 12172 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);
        bug("bye", v, p);
    }
    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
            VS::MO(P+1, v-1, 1);
            toL[v] = P;
            bug(btw, v, P);
        }
    }
}

void updr(int v) {
    if (toR[v]!=-1) {
        int p = toR[v];
        toR[v] = -1;
        VS::MO(v+1,p-1, -1);
    }
    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]) {
            VS::MO(v+1, P-1, 1);
            toR[v] = P;
            bug(v, P);
        }
    }
}

void chg(int v, int val, bool doleft, bool doright) {
    // walk left!!
    BIT::MO(v, val - A[v]); NXTS::MO(v, val);
    A[v] = val;
    updl(v); updr(v);
    if (doleft) {
        for (int u = v-1; u!=-1 && u>=0; u = NXTS::Qright(0,u-1,1+BIT::QU(u,v-1))) {
            updr(u);
        }
    }
    if (doright) {
        for (int u = v+1; u!=-1 && u<n; u = NXTS::Qleft(u+1, maxn-1, 1+BIT::QU(v+1, u))) {
            updl(u);
        }
    }
}

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

    cin>>n;
    n+=2;
    REP1(i,n-2) {
        cin>>A[i];
    }
    ll big = 1e15+10;
    A[0] = A[n-1] = big;
    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;
        if (tp == 2) {
            int tmpl = A[l-1], tmpr = A[r+1];
            chg(l-1, big,1,0); chg(r+1, big,0,1);
            int gt = VS::QU(l,r);
            cout<<gt<<endl;
            chg(l-1, tmpl,1,0); chg(r+1, tmpr,0,1);
        }else{
            chg(l,r,1,1);
        }
    }


}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7996 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 5 ms 8020 KB Output is correct
2 Correct 58 ms 11556 KB Output is correct
3 Correct 61 ms 11640 KB Output is correct
4 Correct 60 ms 11592 KB Output is correct
5 Correct 63 ms 11568 KB Output is correct
6 Correct 56 ms 11548 KB Output is correct
7 Correct 58 ms 11636 KB Output is correct
8 Correct 54 ms 11660 KB Output is correct
9 Correct 43 ms 11596 KB Output is correct
10 Correct 63 ms 11564 KB Output is correct
11 Correct 59 ms 11584 KB Output is correct
12 Correct 57 ms 11636 KB Output is correct
13 Correct 55 ms 11596 KB Output is correct
14 Correct 79 ms 11552 KB Output is correct
15 Correct 56 ms 11652 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8020 KB Output is correct
2 Correct 58 ms 11556 KB Output is correct
3 Correct 61 ms 11640 KB Output is correct
4 Correct 60 ms 11592 KB Output is correct
5 Correct 63 ms 11568 KB Output is correct
6 Correct 56 ms 11548 KB Output is correct
7 Correct 58 ms 11636 KB Output is correct
8 Correct 54 ms 11660 KB Output is correct
9 Correct 43 ms 11596 KB Output is correct
10 Correct 63 ms 11564 KB Output is correct
11 Correct 59 ms 11584 KB Output is correct
12 Correct 57 ms 11636 KB Output is correct
13 Correct 55 ms 11596 KB Output is correct
14 Correct 79 ms 11552 KB Output is correct
15 Correct 56 ms 11652 KB Output is correct
16 Incorrect 5 ms 8020 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8020 KB Output is correct
2 Correct 58 ms 11556 KB Output is correct
3 Correct 61 ms 11640 KB Output is correct
4 Correct 60 ms 11592 KB Output is correct
5 Correct 63 ms 11568 KB Output is correct
6 Correct 56 ms 11548 KB Output is correct
7 Correct 58 ms 11636 KB Output is correct
8 Correct 54 ms 11660 KB Output is correct
9 Correct 43 ms 11596 KB Output is correct
10 Correct 63 ms 11564 KB Output is correct
11 Correct 59 ms 11584 KB Output is correct
12 Correct 57 ms 11636 KB Output is correct
13 Correct 55 ms 11596 KB Output is correct
14 Correct 79 ms 11552 KB Output is correct
15 Correct 56 ms 11652 KB Output is correct
16 Correct 4 ms 8020 KB Output is correct
17 Correct 1480 ms 11676 KB Output is correct
18 Correct 938 ms 11944 KB Output is correct
19 Correct 1253 ms 11964 KB Output is correct
20 Correct 920 ms 11856 KB Output is correct
21 Correct 1324 ms 11728 KB Output is correct
22 Correct 939 ms 11804 KB Output is correct
23 Correct 1323 ms 11708 KB Output is correct
24 Correct 914 ms 11812 KB Output is correct
25 Correct 1295 ms 11892 KB Output is correct
26 Correct 579 ms 11788 KB Output is correct
27 Correct 629 ms 11680 KB Output is correct
28 Correct 779 ms 11996 KB Output is correct
29 Correct 636 ms 11984 KB Output is correct
30 Correct 616 ms 11836 KB Output is correct
31 Correct 777 ms 11904 KB Output is correct
32 Correct 898 ms 11836 KB Output is correct
33 Correct 677 ms 11732 KB Output is correct
34 Correct 938 ms 11684 KB Output is correct
35 Correct 675 ms 11768 KB Output is correct
36 Correct 909 ms 11836 KB Output is correct
37 Correct 889 ms 11728 KB Output is correct
38 Correct 721 ms 11928 KB Output is correct
39 Correct 713 ms 11896 KB Output is correct
40 Correct 625 ms 12172 KB Output is correct

Subtask #6
0 / 17.0

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