oj.uz

Submission #737982

# Submission time Handle Problem Language Result Execution time Memory
737982 2023-05-08T03:44:40 Z resting Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 57956 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mx = 1e5 + 5;
const ll inf = 1e15;


struct segtree2 {
    int l, r, cnt1 = 0, cnt2 = 0, lz = 0;
    segtree2* lc, * rc;
    segtree2* getmem();
    segtree2() : segtree2(-1, -1) {};
    segtree2(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree2(l, m);
        rc = getmem(); *rc = segtree2(m + 1, r);
    }
    void fix() {
        if (l == r) {
            cnt1 = cnt2 = 0;
            if (lz == 1) cnt1 = 1;
            if (lz > 1) cnt2 = 1;
            return;
        }
        if (lz == 0) {
            cnt1 = lc->cnt1 + rc->cnt1;
            cnt2 = lc->cnt2 + rc->cnt2;
        } else if (lz == 1) {
            cnt2 = lc->cnt1 + rc->cnt1 + lc->cnt2 + rc->cnt2;
            cnt1 = (r - l + 1) - cnt2;
        } else {
            cnt1 = 0;
            cnt2 = (r - l + 1);
        }
    }
    void upd(int ql, int qr, int qv) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lz += qv; fix();
            return;
        }
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        fix();
    }
    int q(int ql, int qr, int qlz = 0) {
        if (l > qr || r < ql) return 0;
        lz += qlz; fix();
        int res = 0;
        if (l >= ql && r <= qr) {
            res = cnt2;
        } else {
            res = lc->q(ql, qr, lz) + rc->q(ql, qr, lz);
        }
        lz -= qlz; fix();
        return res;
    }
};
segtree2 mem2[mx * 4];
int memsz2 = 0;
segtree2* segtree2::getmem() { return &mem2[memsz2++]; }
segtree2 ac2;

struct segtree {
    int l, r, v, m;
    segtree* lc, * rc;
    segtree* getmem();
    vector<pair<int, int>> k;
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        m = (l + r) / 2;
        if (l == r)return;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void del(int ql, int qr) {
        if (qr < m) { lc->del(ql, qr); return; }
        if (ql > m) { rc->del(ql, qr); return; }
        k.erase(find(k.begin(), k.end(), pair<int, int>(ql, qr)));
    }
    void add(int ql, int qr) {
        if (qr < m) { lc->add(ql, qr); return; }
        if (ql > m) { rc->add(ql, qr); return; }
        k.push_back({ ql, qr });
    }
    void q(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q(qi);
        else rc->q(qi);
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end();) {
                if (t->first <= qi) {
                    ac2.upd(t->first, t->second, -1);
                    k.erase(t);
                } else ++t;
            }
        } else {
            for (auto t = k.begin(); t != k.end(); ) {
                if (t->second >= qi) {
                    ac2.upd(t->first, t->second, -1);
                    k.erase(t);
                } else ++t;
            }
        }
    }
};
segtree mem[mx * 4];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }


struct segtree3 {
    int l, r; ll mx = 0, sm = 0;
    segtree3* lc, * rc;
    segtree3* getmem();
    segtree3() : segtree3(-1, -1) {};
    segtree3(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree3(l, m);
        rc = getmem(); *rc = segtree3(m + 1, r);
    }
    void fix() {
        if (l == r) return;
        mx = max(lc->mx, rc->mx);
        sm = lc->sm + rc->sm;
    }
    void upd(int qi, ll qv) {
        if (l > qi || r < qi) return;
        if (l == r) {
            mx = qv; sm = qv;return;
        }
        lc->upd(qi, qv); rc->upd(qi, qv);
        fix();
    }
    int walkl(int ql, ll qv) {
        if (r < ql) return -1;
        if (mx <= qv) return -1;
        if (l == r) return l;
        int v = lc->walkl(ql, qv);
        return v == -1 ? rc->walkl(ql, qv) : v;
    }
    int walkr(int qr, ll qv) {
        if (l > qr) return -1;
        if (mx <= qv) return -1;
        if (l == r) return l;
        int v = rc->walkr(qr, qv);
        return v == -1 ? lc->walkr(qr, qv) : v;
    }
    ll qsum(int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return sm;
        return lc->qsum(ql, qr) + rc->qsum(ql, qr);
    }
};
segtree3 mem3[mx * 4];
int memsz3 = 0;
segtree3* segtree3::getmem() { return &mem3[memsz++]; }


segtree ac;  segtree3 ac3; vector<ll> ac4;
int n;

void clear(int i) {
    ac.q(i);
}

void redo(int i, bool extendleft, bool extendright) {
    //cout << "REDO " << i << endl;
    //walking time
    int l = i, r = i;
    while (1) {
        ll t = ac3.qsum(l, r);
        int wr = ac3.walkl(r + 1, t);
        int wl = ac3.walkr(l - 1, t);
        if (wl < i - 1 && !extendleft) break;
        if (wr > i + 1 && !extendright) break;
        if (wl == -1 || wr == -1) break;
        t = ac3.qsum(wl + 1, wr - 1);
        if (ac4[wl] > t && ac4[wr] > t) {
            ac.add(wl + 1, wr - 1);
            ac2.upd(wl + 1, wr - 1, 1);
        }
        l = wl + 1, r = wr - 1;
        if (ac4[wl] > ac4[wr]) {
            if (!extendright) break;
            r++;
        } else {
            if (!extendleft) break;
            l--;
        }
    }
}

void upd(int i, ll v, bool left, bool right) {
    ac4[i] = v; ac3.upd(i, v);
    clear(i);
    if (i < n + 1 && right)clear(i + 1);
    if (i && left)clear(i - 1);

    redo(i, 1, 1);
    if (i < n + 1 && right)redo(i + 1, 0, 1);
    if (i && left)redo(i - 1, 1, 0);
}

void solve() {
    cin >> n;
    vector<int> a(n + 1, 0); for (int i = 1; i <= n; i++) cin >> a[i];
    ac = segtree(0, n + 1); ac2 = segtree2(0, n + 1); ac3 = segtree3(0, n + 1); ac4 = vector<ll>(n + 2, 0);
    for (int i = 0; i <= n + 1; i++) { ac4[i] = a[i]; ac3.upd(i, a[i]); }
    for (int i = 0; i <= n + 1; i++) { redo(i, 1, 0); }
    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y; a[x] = y;
            upd(x, y, 1, 1);
        } else {
            int l, r; cin >> l >> r;
            upd(l - 1, inf, 0, 1); upd(r + 1, inf, 1, 0);
            cout << (r - l + 1 - ac2.q(l, r)) << endl;
            upd(l - 1, a[l - 1], 0, 1); upd(r + 1, a[r + 1], 1, 0);
        }
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53516 KB Output is correct
2 Correct 26 ms 53440 KB Output is correct
3 Correct 28 ms 53524 KB Output is correct
4 Correct 24 ms 53500 KB Output is correct
5 Correct 28 ms 53460 KB Output is correct
6 Correct 33 ms 53460 KB Output is correct
7 Correct 33 ms 53460 KB Output is correct
8 Correct 37 ms 53552 KB Output is correct
9 Correct 32 ms 53552 KB Output is correct
10 Correct 26 ms 53568 KB Output is correct
11 Correct 28 ms 53424 KB Output is correct
12 Correct 27 ms 53468 KB Output is correct
13 Correct 34 ms 53460 KB Output is correct
14 Correct 27 ms 53484 KB Output is correct
15 Correct 29 ms 53476 KB Output is correct
16 Correct 29 ms 53484 KB Output is correct
17 Correct 29 ms 53504 KB Output is correct
18 Correct 31 ms 53544 KB Output is correct
19 Correct 28 ms 53444 KB Output is correct
20 Correct 27 ms 53512 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53424 KB Output is correct
2 Correct 107 ms 55872 KB Output is correct
3 Correct 117 ms 55828 KB Output is correct
4 Correct 108 ms 55756 KB Output is correct
5 Correct 111 ms 55880 KB Output is correct
6 Correct 100 ms 55924 KB Output is correct
7 Correct 96 ms 55344 KB Output is correct
8 Correct 104 ms 56004 KB Output is correct
9 Correct 92 ms 55440 KB Output is correct
10 Correct 141 ms 55140 KB Output is correct
11 Correct 105 ms 55372 KB Output is correct
12 Correct 97 ms 55728 KB Output is correct
13 Correct 105 ms 55788 KB Output is correct
14 Correct 113 ms 56388 KB Output is correct
15 Correct 113 ms 56192 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53516 KB Output is correct
2 Correct 26 ms 53440 KB Output is correct
3 Correct 28 ms 53524 KB Output is correct
4 Correct 24 ms 53500 KB Output is correct
5 Correct 28 ms 53460 KB Output is correct
6 Correct 33 ms 53460 KB Output is correct
7 Correct 33 ms 53460 KB Output is correct
8 Correct 37 ms 53552 KB Output is correct
9 Correct 32 ms 53552 KB Output is correct
10 Correct 26 ms 53568 KB Output is correct
11 Correct 28 ms 53424 KB Output is correct
12 Correct 27 ms 53468 KB Output is correct
13 Correct 34 ms 53460 KB Output is correct
14 Correct 27 ms 53484 KB Output is correct
15 Correct 29 ms 53476 KB Output is correct
16 Correct 29 ms 53484 KB Output is correct
17 Correct 29 ms 53504 KB Output is correct
18 Correct 31 ms 53544 KB Output is correct
19 Correct 28 ms 53444 KB Output is correct
20 Correct 27 ms 53512 KB Output is correct
21 Correct 23 ms 53424 KB Output is correct
22 Correct 107 ms 55872 KB Output is correct
23 Correct 117 ms 55828 KB Output is correct
24 Correct 108 ms 55756 KB Output is correct
25 Correct 111 ms 55880 KB Output is correct
26 Correct 100 ms 55924 KB Output is correct
27 Correct 96 ms 55344 KB Output is correct
28 Correct 104 ms 56004 KB Output is correct
29 Correct 92 ms 55440 KB Output is correct
30 Correct 141 ms 55140 KB Output is correct
31 Correct 105 ms 55372 KB Output is correct
32 Correct 97 ms 55728 KB Output is correct
33 Correct 105 ms 55788 KB Output is correct
34 Correct 113 ms 56388 KB Output is correct
35 Correct 113 ms 56192 KB Output is correct
36 Correct 144 ms 56068 KB Output is correct
37 Correct 160 ms 55960 KB Output is correct
38 Correct 153 ms 55880 KB Output is correct
39 Correct 130 ms 56004 KB Output is correct
40 Correct 150 ms 55888 KB Output is correct
41 Correct 114 ms 55868 KB Output is correct
42 Correct 121 ms 55880 KB Output is correct
43 Correct 132 ms 55500 KB Output is correct
44 Correct 138 ms 55472 KB Output is correct
45 Correct 151 ms 55380 KB Output is correct
46 Correct 143 ms 55228 KB Output is correct
47 Correct 132 ms 55104 KB Output is correct
48 Correct 112 ms 55744 KB Output is correct
49 Correct 124 ms 55708 KB Output is correct
50 Correct 129 ms 56400 KB Output is correct
51 Correct 130 ms 56268 KB Output is correct
52 Correct 129 ms 56412 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53424 KB Output is correct
2 Correct 107 ms 55872 KB Output is correct
3 Correct 117 ms 55828 KB Output is correct
4 Correct 108 ms 55756 KB Output is correct
5 Correct 111 ms 55880 KB Output is correct
6 Correct 100 ms 55924 KB Output is correct
7 Correct 96 ms 55344 KB Output is correct
8 Correct 104 ms 56004 KB Output is correct
9 Correct 92 ms 55440 KB Output is correct
10 Correct 141 ms 55140 KB Output is correct
11 Correct 105 ms 55372 KB Output is correct
12 Correct 97 ms 55728 KB Output is correct
13 Correct 105 ms 55788 KB Output is correct
14 Correct 113 ms 56388 KB Output is correct
15 Correct 113 ms 56192 KB Output is correct
16 Correct 24 ms 53424 KB Output is correct
17 Execution timed out 4069 ms 57356 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53424 KB Output is correct
2 Correct 107 ms 55872 KB Output is correct
3 Correct 117 ms 55828 KB Output is correct
4 Correct 108 ms 55756 KB Output is correct
5 Correct 111 ms 55880 KB Output is correct
6 Correct 100 ms 55924 KB Output is correct
7 Correct 96 ms 55344 KB Output is correct
8 Correct 104 ms 56004 KB Output is correct
9 Correct 92 ms 55440 KB Output is correct
10 Correct 141 ms 55140 KB Output is correct
11 Correct 105 ms 55372 KB Output is correct
12 Correct 97 ms 55728 KB Output is correct
13 Correct 105 ms 55788 KB Output is correct
14 Correct 113 ms 56388 KB Output is correct
15 Correct 113 ms 56192 KB Output is correct
16 Correct 24 ms 53460 KB Output is correct
17 Correct 1046 ms 56196 KB Output is correct
18 Correct 1071 ms 57880 KB Output is correct
19 Correct 1718 ms 56140 KB Output is correct
20 Correct 1195 ms 57824 KB Output is correct
21 Correct 1299 ms 56124 KB Output is correct
22 Correct 1098 ms 57860 KB Output is correct
23 Correct 1289 ms 56260 KB Output is correct
24 Correct 1077 ms 57956 KB Output is correct
25 Correct 1384 ms 56120 KB Output is correct
26 Correct 737 ms 56660 KB Output is correct
27 Correct 686 ms 56664 KB Output is correct
28 Correct 999 ms 56988 KB Output is correct
29 Correct 720 ms 56816 KB Output is correct
30 Correct 696 ms 56692 KB Output is correct
31 Correct 1032 ms 57024 KB Output is correct
32 Correct 1024 ms 57308 KB Output is correct
33 Correct 742 ms 55708 KB Output is correct
34 Correct 1040 ms 57676 KB Output is correct
35 Correct 875 ms 55416 KB Output is correct
36 Correct 1058 ms 57168 KB Output is correct
37 Correct 1035 ms 56880 KB Output is correct
38 Correct 1085 ms 56632 KB Output is correct
39 Correct 868 ms 57156 KB Output is correct
40 Correct 879 ms 56984 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53516 KB Output is correct
2 Correct 26 ms 53440 KB Output is correct
3 Correct 28 ms 53524 KB Output is correct
4 Correct 24 ms 53500 KB Output is correct
5 Correct 28 ms 53460 KB Output is correct
6 Correct 33 ms 53460 KB Output is correct
7 Correct 33 ms 53460 KB Output is correct
8 Correct 37 ms 53552 KB Output is correct
9 Correct 32 ms 53552 KB Output is correct
10 Correct 26 ms 53568 KB Output is correct
11 Correct 28 ms 53424 KB Output is correct
12 Correct 27 ms 53468 KB Output is correct
13 Correct 34 ms 53460 KB Output is correct
14 Correct 27 ms 53484 KB Output is correct
15 Correct 29 ms 53476 KB Output is correct
16 Correct 29 ms 53484 KB Output is correct
17 Correct 29 ms 53504 KB Output is correct
18 Correct 31 ms 53544 KB Output is correct
19 Correct 28 ms 53444 KB Output is correct
20 Correct 27 ms 53512 KB Output is correct
21 Correct 23 ms 53424 KB Output is correct
22 Correct 107 ms 55872 KB Output is correct
23 Correct 117 ms 55828 KB Output is correct
24 Correct 108 ms 55756 KB Output is correct
25 Correct 111 ms 55880 KB Output is correct
26 Correct 100 ms 55924 KB Output is correct
27 Correct 96 ms 55344 KB Output is correct
28 Correct 104 ms 56004 KB Output is correct
29 Correct 92 ms 55440 KB Output is correct
30 Correct 141 ms 55140 KB Output is correct
31 Correct 105 ms 55372 KB Output is correct
32 Correct 97 ms 55728 KB Output is correct
33 Correct 105 ms 55788 KB Output is correct
34 Correct 113 ms 56388 KB Output is correct
35 Correct 113 ms 56192 KB Output is correct
36 Correct 144 ms 56068 KB Output is correct
37 Correct 160 ms 55960 KB Output is correct
38 Correct 153 ms 55880 KB Output is correct
39 Correct 130 ms 56004 KB Output is correct
40 Correct 150 ms 55888 KB Output is correct
41 Correct 114 ms 55868 KB Output is correct
42 Correct 121 ms 55880 KB Output is correct
43 Correct 132 ms 55500 KB Output is correct
44 Correct 138 ms 55472 KB Output is correct
45 Correct 151 ms 55380 KB Output is correct
46 Correct 143 ms 55228 KB Output is correct
47 Correct 132 ms 55104 KB Output is correct
48 Correct 112 ms 55744 KB Output is correct
49 Correct 124 ms 55708 KB Output is correct
50 Correct 129 ms 56400 KB Output is correct
51 Correct 130 ms 56268 KB Output is correct
52 Correct 129 ms 56412 KB Output is correct
53 Correct 24 ms 53424 KB Output is correct
54 Execution timed out 4069 ms 57356 KB Time limit exceeded
55 Halted 0 ms 0 KB -