oj.uz

Submission #590579

# Submission time Handle Problem Language Result Execution time Memory
590579 2022-07-06T06:53:49 Z balbit Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 24952 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));
        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
            fromR[P].pb(v);
            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);
        fromL[p].erase(find(ALL(fromL[p]), v));
        bug("bye", v, p);
    }
    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);
        }
    }
}

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

    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); chg(r+1, big);
            int gt = VS::QU(l,r);
            cout<<gt<<endl;
            chg(l-1, tmpl); chg(r+1, tmpr);
        }else{
            chg(l,r);
        }
    }


}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 9 ms 12716 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 20 ms 12884 KB Output is correct
6 Correct 29 ms 12884 KB Output is correct
7 Correct 18 ms 12884 KB Output is correct
8 Correct 41 ms 12884 KB Output is correct
9 Correct 29 ms 12908 KB Output is correct
10 Correct 13 ms 12884 KB Output is correct
11 Correct 18 ms 12884 KB Output is correct
12 Correct 13 ms 12884 KB Output is correct
13 Correct 22 ms 12892 KB Output is correct
14 Correct 17 ms 12884 KB Output is correct
15 Correct 27 ms 12912 KB Output is correct
16 Correct 28 ms 12840 KB Output is correct
17 Correct 17 ms 12884 KB Output is correct
18 Correct 24 ms 12840 KB Output is correct
19 Correct 14 ms 12904 KB Output is correct
20 Correct 18 ms 12888 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12712 KB Output is correct
2 Correct 67 ms 17688 KB Output is correct
3 Correct 82 ms 18116 KB Output is correct
4 Correct 72 ms 17868 KB Output is correct
5 Correct 71 ms 17980 KB Output is correct
6 Correct 76 ms 18460 KB Output is correct
7 Correct 58 ms 17360 KB Output is correct
8 Correct 65 ms 18500 KB Output is correct
9 Correct 50 ms 17340 KB Output is correct
10 Correct 77 ms 19420 KB Output is correct
11 Correct 68 ms 18960 KB Output is correct
12 Correct 56 ms 17780 KB Output is correct
13 Correct 59 ms 17716 KB Output is correct
14 Correct 67 ms 18684 KB Output is correct
15 Correct 70 ms 18564 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 9 ms 12716 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 20 ms 12884 KB Output is correct
6 Correct 29 ms 12884 KB Output is correct
7 Correct 18 ms 12884 KB Output is correct
8 Correct 41 ms 12884 KB Output is correct
9 Correct 29 ms 12908 KB Output is correct
10 Correct 13 ms 12884 KB Output is correct
11 Correct 18 ms 12884 KB Output is correct
12 Correct 13 ms 12884 KB Output is correct
13 Correct 22 ms 12892 KB Output is correct
14 Correct 17 ms 12884 KB Output is correct
15 Correct 27 ms 12912 KB Output is correct
16 Correct 28 ms 12840 KB Output is correct
17 Correct 17 ms 12884 KB Output is correct
18 Correct 24 ms 12840 KB Output is correct
19 Correct 14 ms 12904 KB Output is correct
20 Correct 18 ms 12888 KB Output is correct
21 Correct 8 ms 12712 KB Output is correct
22 Correct 67 ms 17688 KB Output is correct
23 Correct 82 ms 18116 KB Output is correct
24 Correct 72 ms 17868 KB Output is correct
25 Correct 71 ms 17980 KB Output is correct
26 Correct 76 ms 18460 KB Output is correct
27 Correct 58 ms 17360 KB Output is correct
28 Correct 65 ms 18500 KB Output is correct
29 Correct 50 ms 17340 KB Output is correct
30 Correct 77 ms 19420 KB Output is correct
31 Correct 68 ms 18960 KB Output is correct
32 Correct 56 ms 17780 KB Output is correct
33 Correct 59 ms 17716 KB Output is correct
34 Correct 67 ms 18684 KB Output is correct
35 Correct 70 ms 18564 KB Output is correct
36 Correct 121 ms 18100 KB Output is correct
37 Correct 167 ms 18144 KB Output is correct
38 Correct 149 ms 17996 KB Output is correct
39 Correct 105 ms 18084 KB Output is correct
40 Correct 144 ms 18196 KB Output is correct
41 Correct 89 ms 18648 KB Output is correct
42 Correct 110 ms 18608 KB Output is correct
43 Correct 97 ms 17528 KB Output is correct
44 Correct 118 ms 17696 KB Output is correct
45 Correct 142 ms 20012 KB Output is correct
46 Correct 121 ms 19604 KB Output is correct
47 Correct 133 ms 18060 KB Output is correct
48 Correct 77 ms 17828 KB Output is correct
49 Correct 103 ms 17852 KB Output is correct
50 Correct 91 ms 18756 KB Output is correct
51 Correct 94 ms 18672 KB Output is correct
52 Correct 98 ms 18832 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12712 KB Output is correct
2 Correct 67 ms 17688 KB Output is correct
3 Correct 82 ms 18116 KB Output is correct
4 Correct 72 ms 17868 KB Output is correct
5 Correct 71 ms 17980 KB Output is correct
6 Correct 76 ms 18460 KB Output is correct
7 Correct 58 ms 17360 KB Output is correct
8 Correct 65 ms 18500 KB Output is correct
9 Correct 50 ms 17340 KB Output is correct
10 Correct 77 ms 19420 KB Output is correct
11 Correct 68 ms 18960 KB Output is correct
12 Correct 56 ms 17780 KB Output is correct
13 Correct 59 ms 17716 KB Output is correct
14 Correct 67 ms 18684 KB Output is correct
15 Correct 70 ms 18564 KB Output is correct
16 Correct 7 ms 12756 KB Output is correct
17 Execution timed out 4045 ms 24952 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12712 KB Output is correct
2 Correct 67 ms 17688 KB Output is correct
3 Correct 82 ms 18116 KB Output is correct
4 Correct 72 ms 17868 KB Output is correct
5 Correct 71 ms 17980 KB Output is correct
6 Correct 76 ms 18460 KB Output is correct
7 Correct 58 ms 17360 KB Output is correct
8 Correct 65 ms 18500 KB Output is correct
9 Correct 50 ms 17340 KB Output is correct
10 Correct 77 ms 19420 KB Output is correct
11 Correct 68 ms 18960 KB Output is correct
12 Correct 56 ms 17780 KB Output is correct
13 Correct 59 ms 17716 KB Output is correct
14 Correct 67 ms 18684 KB Output is correct
15 Correct 70 ms 18564 KB Output is correct
16 Correct 9 ms 12756 KB Output is correct
17 Correct 2143 ms 19184 KB Output is correct
18 Correct 1182 ms 23356 KB Output is correct
19 Correct 3068 ms 19452 KB Output is correct
20 Correct 1527 ms 22904 KB Output is correct
21 Correct 1561 ms 19536 KB Output is correct
22 Correct 1250 ms 23312 KB Output is correct
23 Correct 1814 ms 19300 KB Output is correct
24 Correct 1221 ms 23192 KB Output is correct
25 Correct 2024 ms 19408 KB Output is correct
26 Correct 939 ms 21092 KB Output is correct
27 Correct 761 ms 21628 KB Output is correct
28 Correct 1240 ms 21192 KB Output is correct
29 Correct 928 ms 21336 KB Output is correct
30 Correct 749 ms 21460 KB Output is correct
31 Correct 1233 ms 21544 KB Output is correct
32 Correct 1146 ms 23624 KB Output is correct
33 Correct 1170 ms 20328 KB Output is correct
34 Correct 1174 ms 24452 KB Output is correct
35 Correct 1550 ms 20832 KB Output is correct
36 Correct 1213 ms 23140 KB Output is correct
37 Correct 1255 ms 20712 KB Output is correct
38 Correct 1561 ms 20116 KB Output is correct
39 Correct 1047 ms 21428 KB Output is correct
40 Correct 1411 ms 20828 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12756 KB Output is correct
2 Correct 9 ms 12716 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 20 ms 12884 KB Output is correct
6 Correct 29 ms 12884 KB Output is correct
7 Correct 18 ms 12884 KB Output is correct
8 Correct 41 ms 12884 KB Output is correct
9 Correct 29 ms 12908 KB Output is correct
10 Correct 13 ms 12884 KB Output is correct
11 Correct 18 ms 12884 KB Output is correct
12 Correct 13 ms 12884 KB Output is correct
13 Correct 22 ms 12892 KB Output is correct
14 Correct 17 ms 12884 KB Output is correct
15 Correct 27 ms 12912 KB Output is correct
16 Correct 28 ms 12840 KB Output is correct
17 Correct 17 ms 12884 KB Output is correct
18 Correct 24 ms 12840 KB Output is correct
19 Correct 14 ms 12904 KB Output is correct
20 Correct 18 ms 12888 KB Output is correct
21 Correct 8 ms 12712 KB Output is correct
22 Correct 67 ms 17688 KB Output is correct
23 Correct 82 ms 18116 KB Output is correct
24 Correct 72 ms 17868 KB Output is correct
25 Correct 71 ms 17980 KB Output is correct
26 Correct 76 ms 18460 KB Output is correct
27 Correct 58 ms 17360 KB Output is correct
28 Correct 65 ms 18500 KB Output is correct
29 Correct 50 ms 17340 KB Output is correct
30 Correct 77 ms 19420 KB Output is correct
31 Correct 68 ms 18960 KB Output is correct
32 Correct 56 ms 17780 KB Output is correct
33 Correct 59 ms 17716 KB Output is correct
34 Correct 67 ms 18684 KB Output is correct
35 Correct 70 ms 18564 KB Output is correct
36 Correct 121 ms 18100 KB Output is correct
37 Correct 167 ms 18144 KB Output is correct
38 Correct 149 ms 17996 KB Output is correct
39 Correct 105 ms 18084 KB Output is correct
40 Correct 144 ms 18196 KB Output is correct
41 Correct 89 ms 18648 KB Output is correct
42 Correct 110 ms 18608 KB Output is correct
43 Correct 97 ms 17528 KB Output is correct
44 Correct 118 ms 17696 KB Output is correct
45 Correct 142 ms 20012 KB Output is correct
46 Correct 121 ms 19604 KB Output is correct
47 Correct 133 ms 18060 KB Output is correct
48 Correct 77 ms 17828 KB Output is correct
49 Correct 103 ms 17852 KB Output is correct
50 Correct 91 ms 18756 KB Output is correct
51 Correct 94 ms 18672 KB Output is correct
52 Correct 98 ms 18832 KB Output is correct
53 Correct 7 ms 12756 KB Output is correct
54 Execution timed out 4045 ms 24952 KB Time limit exceeded
55 Halted 0 ms 0 KB -