oj.uz

Submission #737968

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

#define ll long long

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

vector<pair<int, int>> res;
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);
        vector<pair<int, int>> rem;
        if (qi <= m) {
            for (auto t = k.begin(); t != k.end(); t++) {
                if (t->first <= qi)
                    res.push_back(*t);
                else
                    rem.push_back(*t);
            }
        } else {
            for (auto t = k.rbegin(); t != k.rend(); t++) {
                if (t->second >= qi)
                    res.push_back(*t);
                else
                    rem.push_back(*t);
            }
        }
        k = rem;
    }
};
segtree mem[mx * 4];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }

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++]; }

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; segtree2 ac2; segtree3 ac3; vector<ll> ac4;
int n;

void clear(int i) {
    res.clear(); ac.q(i);
    for (auto& x : res) {
        auto [l, r] = x;
        //cout << "DEL " << l << " " << r << endl;
        //ac.del(l, r);
        ac2.upd(l, r, -1);
    }
}

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;
        //cout << l << "," << r << "," << wl << "," << wr << endl;
        if (wl == -1 || wr == -1) break;
        t = ac3.qsum(wl + 1, wr - 1);
        if (ac4[wl] > t && ac4[wr] > t) {
            //cout << "ADD " << wl + 1 << " " << wr - 1 << " " << t << " " << ac4[wl] << " " << ac4[wr] << endl;
            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++) upd(i, a[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 53460 KB Output is correct
2 Correct 24 ms 53468 KB Output is correct
3 Correct 24 ms 53460 KB Output is correct
4 Correct 24 ms 53540 KB Output is correct
5 Correct 31 ms 53448 KB Output is correct
6 Correct 34 ms 53524 KB Output is correct
7 Correct 30 ms 53500 KB Output is correct
8 Correct 37 ms 53460 KB Output is correct
9 Correct 36 ms 53548 KB Output is correct
10 Correct 28 ms 53520 KB Output is correct
11 Correct 29 ms 53472 KB Output is correct
12 Correct 28 ms 53568 KB Output is correct
13 Correct 33 ms 53552 KB Output is correct
14 Correct 29 ms 53460 KB Output is correct
15 Correct 30 ms 53508 KB Output is correct
16 Correct 30 ms 53500 KB Output is correct
17 Correct 29 ms 53548 KB Output is correct
18 Correct 32 ms 53552 KB Output is correct
19 Correct 30 ms 53460 KB Output is correct
20 Correct 28 ms 53460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53460 KB Output is correct
2 Correct 319 ms 55948 KB Output is correct
3 Correct 351 ms 55888 KB Output is correct
4 Correct 342 ms 55840 KB Output is correct
5 Correct 346 ms 55884 KB Output is correct
6 Correct 168 ms 55992 KB Output is correct
7 Correct 169 ms 55556 KB Output is correct
8 Correct 176 ms 55884 KB Output is correct
9 Correct 167 ms 55456 KB Output is correct
10 Correct 267 ms 55200 KB Output is correct
11 Correct 289 ms 55404 KB Output is correct
12 Correct 175 ms 55784 KB Output is correct
13 Correct 165 ms 55792 KB Output is correct
14 Correct 197 ms 56396 KB Output is correct
15 Correct 201 ms 56304 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53460 KB Output is correct
2 Correct 24 ms 53468 KB Output is correct
3 Correct 24 ms 53460 KB Output is correct
4 Correct 24 ms 53540 KB Output is correct
5 Correct 31 ms 53448 KB Output is correct
6 Correct 34 ms 53524 KB Output is correct
7 Correct 30 ms 53500 KB Output is correct
8 Correct 37 ms 53460 KB Output is correct
9 Correct 36 ms 53548 KB Output is correct
10 Correct 28 ms 53520 KB Output is correct
11 Correct 29 ms 53472 KB Output is correct
12 Correct 28 ms 53568 KB Output is correct
13 Correct 33 ms 53552 KB Output is correct
14 Correct 29 ms 53460 KB Output is correct
15 Correct 30 ms 53508 KB Output is correct
16 Correct 30 ms 53500 KB Output is correct
17 Correct 29 ms 53548 KB Output is correct
18 Correct 32 ms 53552 KB Output is correct
19 Correct 30 ms 53460 KB Output is correct
20 Correct 28 ms 53460 KB Output is correct
21 Correct 23 ms 53460 KB Output is correct
22 Correct 319 ms 55948 KB Output is correct
23 Correct 351 ms 55888 KB Output is correct
24 Correct 342 ms 55840 KB Output is correct
25 Correct 346 ms 55884 KB Output is correct
26 Correct 168 ms 55992 KB Output is correct
27 Correct 169 ms 55556 KB Output is correct
28 Correct 176 ms 55884 KB Output is correct
29 Correct 167 ms 55456 KB Output is correct
30 Correct 267 ms 55200 KB Output is correct
31 Correct 289 ms 55404 KB Output is correct
32 Correct 175 ms 55784 KB Output is correct
33 Correct 165 ms 55792 KB Output is correct
34 Correct 197 ms 56396 KB Output is correct
35 Correct 201 ms 56304 KB Output is correct
36 Correct 388 ms 56012 KB Output is correct
37 Correct 389 ms 56052 KB Output is correct
38 Correct 380 ms 55872 KB Output is correct
39 Correct 367 ms 56092 KB Output is correct
40 Correct 390 ms 55892 KB Output is correct
41 Correct 184 ms 55856 KB Output is correct
42 Correct 183 ms 55896 KB Output is correct
43 Correct 216 ms 55480 KB Output is correct
44 Correct 223 ms 55372 KB Output is correct
45 Correct 351 ms 55392 KB Output is correct
46 Correct 323 ms 55244 KB Output is correct
47 Correct 294 ms 55224 KB Output is correct
48 Correct 197 ms 55812 KB Output is correct
49 Correct 198 ms 55936 KB Output is correct
50 Correct 224 ms 56396 KB Output is correct
51 Correct 228 ms 56216 KB Output is correct
52 Correct 226 ms 56432 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53460 KB Output is correct
2 Correct 319 ms 55948 KB Output is correct
3 Correct 351 ms 55888 KB Output is correct
4 Correct 342 ms 55840 KB Output is correct
5 Correct 346 ms 55884 KB Output is correct
6 Correct 168 ms 55992 KB Output is correct
7 Correct 169 ms 55556 KB Output is correct
8 Correct 176 ms 55884 KB Output is correct
9 Correct 167 ms 55456 KB Output is correct
10 Correct 267 ms 55200 KB Output is correct
11 Correct 289 ms 55404 KB Output is correct
12 Correct 175 ms 55784 KB Output is correct
13 Correct 165 ms 55792 KB Output is correct
14 Correct 197 ms 56396 KB Output is correct
15 Correct 201 ms 56304 KB Output is correct
16 Correct 27 ms 53460 KB Output is correct
17 Execution timed out 4070 ms 56896 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 53460 KB Output is correct
2 Correct 319 ms 55948 KB Output is correct
3 Correct 351 ms 55888 KB Output is correct
4 Correct 342 ms 55840 KB Output is correct
5 Correct 346 ms 55884 KB Output is correct
6 Correct 168 ms 55992 KB Output is correct
7 Correct 169 ms 55556 KB Output is correct
8 Correct 176 ms 55884 KB Output is correct
9 Correct 167 ms 55456 KB Output is correct
10 Correct 267 ms 55200 KB Output is correct
11 Correct 289 ms 55404 KB Output is correct
12 Correct 175 ms 55784 KB Output is correct
13 Correct 165 ms 55792 KB Output is correct
14 Correct 197 ms 56396 KB Output is correct
15 Correct 201 ms 56304 KB Output is correct
16 Correct 23 ms 53460 KB Output is correct
17 Correct 1542 ms 56064 KB Output is correct
18 Correct 1711 ms 57812 KB Output is correct
19 Correct 2723 ms 56184 KB Output is correct
20 Correct 1969 ms 57904 KB Output is correct
21 Correct 1791 ms 56136 KB Output is correct
22 Correct 1644 ms 57908 KB Output is correct
23 Correct 2157 ms 56156 KB Output is correct
24 Correct 1754 ms 57852 KB Output is correct
25 Correct 2227 ms 56276 KB Output is correct
26 Correct 943 ms 56820 KB Output is correct
27 Correct 856 ms 56848 KB Output is correct
28 Correct 1467 ms 56996 KB Output is correct
29 Correct 935 ms 56812 KB Output is correct
30 Correct 864 ms 56764 KB Output is correct
31 Correct 1340 ms 57000 KB Output is correct
32 Correct 1532 ms 57292 KB Output is correct
33 Correct 1435 ms 55772 KB Output is correct
34 Correct 1562 ms 57728 KB Output is correct
35 Correct 1523 ms 55504 KB Output is correct
36 Correct 1709 ms 57164 KB Output is correct
37 Correct 1445 ms 56672 KB Output is correct
38 Correct 1597 ms 56664 KB Output is correct
39 Correct 1199 ms 57256 KB Output is correct
40 Correct 1330 ms 56884 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53460 KB Output is correct
2 Correct 24 ms 53468 KB Output is correct
3 Correct 24 ms 53460 KB Output is correct
4 Correct 24 ms 53540 KB Output is correct
5 Correct 31 ms 53448 KB Output is correct
6 Correct 34 ms 53524 KB Output is correct
7 Correct 30 ms 53500 KB Output is correct
8 Correct 37 ms 53460 KB Output is correct
9 Correct 36 ms 53548 KB Output is correct
10 Correct 28 ms 53520 KB Output is correct
11 Correct 29 ms 53472 KB Output is correct
12 Correct 28 ms 53568 KB Output is correct
13 Correct 33 ms 53552 KB Output is correct
14 Correct 29 ms 53460 KB Output is correct
15 Correct 30 ms 53508 KB Output is correct
16 Correct 30 ms 53500 KB Output is correct
17 Correct 29 ms 53548 KB Output is correct
18 Correct 32 ms 53552 KB Output is correct
19 Correct 30 ms 53460 KB Output is correct
20 Correct 28 ms 53460 KB Output is correct
21 Correct 23 ms 53460 KB Output is correct
22 Correct 319 ms 55948 KB Output is correct
23 Correct 351 ms 55888 KB Output is correct
24 Correct 342 ms 55840 KB Output is correct
25 Correct 346 ms 55884 KB Output is correct
26 Correct 168 ms 55992 KB Output is correct
27 Correct 169 ms 55556 KB Output is correct
28 Correct 176 ms 55884 KB Output is correct
29 Correct 167 ms 55456 KB Output is correct
30 Correct 267 ms 55200 KB Output is correct
31 Correct 289 ms 55404 KB Output is correct
32 Correct 175 ms 55784 KB Output is correct
33 Correct 165 ms 55792 KB Output is correct
34 Correct 197 ms 56396 KB Output is correct
35 Correct 201 ms 56304 KB Output is correct
36 Correct 388 ms 56012 KB Output is correct
37 Correct 389 ms 56052 KB Output is correct
38 Correct 380 ms 55872 KB Output is correct
39 Correct 367 ms 56092 KB Output is correct
40 Correct 390 ms 55892 KB Output is correct
41 Correct 184 ms 55856 KB Output is correct
42 Correct 183 ms 55896 KB Output is correct
43 Correct 216 ms 55480 KB Output is correct
44 Correct 223 ms 55372 KB Output is correct
45 Correct 351 ms 55392 KB Output is correct
46 Correct 323 ms 55244 KB Output is correct
47 Correct 294 ms 55224 KB Output is correct
48 Correct 197 ms 55812 KB Output is correct
49 Correct 198 ms 55936 KB Output is correct
50 Correct 224 ms 56396 KB Output is correct
51 Correct 228 ms 56216 KB Output is correct
52 Correct 226 ms 56432 KB Output is correct
53 Correct 27 ms 53460 KB Output is correct
54 Execution timed out 4070 ms 56896 KB Time limit exceeded
55 Halted 0 ms 0 KB -