oj.uz

Submission #737961

# Submission time Handle Problem Language Result Execution time Memory
737961 2023-05-08T03:09:53 Z resting Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 91968 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();
    set<pair<int, int>> lm, rm;
    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; }
        lm.erase({ ql, qr });
        rm.erase({ qr, ql });
    }
    void add(int ql, int qr) {
        if (qr < m) { lc->add(ql, qr); return; }
        if (ql > m) { rc->add(ql, qr); return; }
        lm.insert({ ql, qr });
        rm.insert({ qr, ql });
    }
    void q(int qi) {
        if (l == r)return;
        if (qi <= m)lc->q(qi);
        else rc->q(qi);
        if (qi <= m) {
            for (auto t = lm.begin(); t != lm.end() && t->first <= qi; t++)
                res.push_back(*t);
        } else {
            for (auto t = rm.rbegin(); t != rm.rend() && t->first >= qi; t++)
                res.push_back({ t->second, t->first });
        }
    }
};
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 42 ms 81696 KB Output is correct
2 Correct 35 ms 81696 KB Output is correct
3 Correct 35 ms 81688 KB Output is correct
4 Correct 36 ms 81656 KB Output is correct
5 Correct 42 ms 81752 KB Output is correct
6 Correct 45 ms 81704 KB Output is correct
7 Correct 42 ms 81716 KB Output is correct
8 Correct 53 ms 81704 KB Output is correct
9 Correct 48 ms 81656 KB Output is correct
10 Correct 40 ms 81672 KB Output is correct
11 Correct 41 ms 81748 KB Output is correct
12 Correct 39 ms 81740 KB Output is correct
13 Correct 46 ms 81748 KB Output is correct
14 Correct 40 ms 81692 KB Output is correct
15 Correct 45 ms 81740 KB Output is correct
16 Correct 43 ms 81724 KB Output is correct
17 Correct 41 ms 81752 KB Output is correct
18 Correct 47 ms 81664 KB Output is correct
19 Correct 39 ms 81736 KB Output is correct
20 Correct 42 ms 81740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81692 KB Output is correct
2 Correct 189 ms 90884 KB Output is correct
3 Correct 185 ms 89920 KB Output is correct
4 Correct 199 ms 90952 KB Output is correct
5 Correct 205 ms 90068 KB Output is correct
6 Correct 188 ms 87016 KB Output is correct
7 Correct 158 ms 85196 KB Output is correct
8 Correct 167 ms 86980 KB Output is correct
9 Correct 167 ms 85336 KB Output is correct
10 Correct 178 ms 86532 KB Output is correct
11 Correct 169 ms 86360 KB Output is correct
12 Correct 161 ms 86508 KB Output is correct
13 Correct 158 ms 86624 KB Output is correct
14 Correct 178 ms 89148 KB Output is correct
15 Correct 182 ms 89204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 81696 KB Output is correct
2 Correct 35 ms 81696 KB Output is correct
3 Correct 35 ms 81688 KB Output is correct
4 Correct 36 ms 81656 KB Output is correct
5 Correct 42 ms 81752 KB Output is correct
6 Correct 45 ms 81704 KB Output is correct
7 Correct 42 ms 81716 KB Output is correct
8 Correct 53 ms 81704 KB Output is correct
9 Correct 48 ms 81656 KB Output is correct
10 Correct 40 ms 81672 KB Output is correct
11 Correct 41 ms 81748 KB Output is correct
12 Correct 39 ms 81740 KB Output is correct
13 Correct 46 ms 81748 KB Output is correct
14 Correct 40 ms 81692 KB Output is correct
15 Correct 45 ms 81740 KB Output is correct
16 Correct 43 ms 81724 KB Output is correct
17 Correct 41 ms 81752 KB Output is correct
18 Correct 47 ms 81664 KB Output is correct
19 Correct 39 ms 81736 KB Output is correct
20 Correct 42 ms 81740 KB Output is correct
21 Correct 36 ms 81692 KB Output is correct
22 Correct 189 ms 90884 KB Output is correct
23 Correct 185 ms 89920 KB Output is correct
24 Correct 199 ms 90952 KB Output is correct
25 Correct 205 ms 90068 KB Output is correct
26 Correct 188 ms 87016 KB Output is correct
27 Correct 158 ms 85196 KB Output is correct
28 Correct 167 ms 86980 KB Output is correct
29 Correct 167 ms 85336 KB Output is correct
30 Correct 178 ms 86532 KB Output is correct
31 Correct 169 ms 86360 KB Output is correct
32 Correct 161 ms 86508 KB Output is correct
33 Correct 158 ms 86624 KB Output is correct
34 Correct 178 ms 89148 KB Output is correct
35 Correct 182 ms 89204 KB Output is correct
36 Correct 252 ms 91936 KB Output is correct
37 Correct 243 ms 90256 KB Output is correct
38 Correct 243 ms 89288 KB Output is correct
39 Correct 227 ms 91968 KB Output is correct
40 Correct 236 ms 89160 KB Output is correct
41 Correct 197 ms 86992 KB Output is correct
42 Correct 193 ms 86916 KB Output is correct
43 Correct 203 ms 85348 KB Output is correct
44 Correct 224 ms 85324 KB Output is correct
45 Correct 234 ms 87344 KB Output is correct
46 Correct 225 ms 86732 KB Output is correct
47 Correct 202 ms 84740 KB Output is correct
48 Correct 182 ms 86536 KB Output is correct
49 Correct 200 ms 86484 KB Output is correct
50 Correct 196 ms 89220 KB Output is correct
51 Correct 219 ms 89164 KB Output is correct
52 Correct 209 ms 89168 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81692 KB Output is correct
2 Correct 189 ms 90884 KB Output is correct
3 Correct 185 ms 89920 KB Output is correct
4 Correct 199 ms 90952 KB Output is correct
5 Correct 205 ms 90068 KB Output is correct
6 Correct 188 ms 87016 KB Output is correct
7 Correct 158 ms 85196 KB Output is correct
8 Correct 167 ms 86980 KB Output is correct
9 Correct 167 ms 85336 KB Output is correct
10 Correct 178 ms 86532 KB Output is correct
11 Correct 169 ms 86360 KB Output is correct
12 Correct 161 ms 86508 KB Output is correct
13 Correct 158 ms 86624 KB Output is correct
14 Correct 178 ms 89148 KB Output is correct
15 Correct 182 ms 89204 KB Output is correct
16 Correct 39 ms 81612 KB Output is correct
17 Execution timed out 4033 ms 90668 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81692 KB Output is correct
2 Correct 189 ms 90884 KB Output is correct
3 Correct 185 ms 89920 KB Output is correct
4 Correct 199 ms 90952 KB Output is correct
5 Correct 205 ms 90068 KB Output is correct
6 Correct 188 ms 87016 KB Output is correct
7 Correct 158 ms 85196 KB Output is correct
8 Correct 167 ms 86980 KB Output is correct
9 Correct 167 ms 85336 KB Output is correct
10 Correct 178 ms 86532 KB Output is correct
11 Correct 169 ms 86360 KB Output is correct
12 Correct 161 ms 86508 KB Output is correct
13 Correct 158 ms 86624 KB Output is correct
14 Correct 178 ms 89148 KB Output is correct
15 Correct 182 ms 89204 KB Output is correct
16 Correct 37 ms 81764 KB Output is correct
17 Correct 1324 ms 90988 KB Output is correct
18 Correct 1446 ms 91172 KB Output is correct
19 Correct 2178 ms 90344 KB Output is correct
20 Correct 1491 ms 91312 KB Output is correct
21 Correct 1683 ms 91012 KB Output is correct
22 Correct 1373 ms 91324 KB Output is correct
23 Correct 1699 ms 90656 KB Output is correct
24 Correct 1404 ms 91080 KB Output is correct
25 Correct 1765 ms 90356 KB Output is correct
26 Correct 884 ms 87452 KB Output is correct
27 Correct 831 ms 87192 KB Output is correct
28 Correct 1229 ms 89068 KB Output is correct
29 Correct 857 ms 87084 KB Output is correct
30 Correct 832 ms 87276 KB Output is correct
31 Correct 1260 ms 88748 KB Output is correct
32 Correct 1319 ms 89536 KB Output is correct
33 Correct 859 ms 86448 KB Output is correct
34 Correct 1299 ms 90472 KB Output is correct
35 Correct 1050 ms 86808 KB Output is correct
36 Correct 1307 ms 89392 KB Output is correct
37 Correct 1335 ms 88924 KB Output is correct
38 Correct 1359 ms 88616 KB Output is correct
39 Correct 1016 ms 89632 KB Output is correct
40 Correct 1027 ms 89628 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 81696 KB Output is correct
2 Correct 35 ms 81696 KB Output is correct
3 Correct 35 ms 81688 KB Output is correct
4 Correct 36 ms 81656 KB Output is correct
5 Correct 42 ms 81752 KB Output is correct
6 Correct 45 ms 81704 KB Output is correct
7 Correct 42 ms 81716 KB Output is correct
8 Correct 53 ms 81704 KB Output is correct
9 Correct 48 ms 81656 KB Output is correct
10 Correct 40 ms 81672 KB Output is correct
11 Correct 41 ms 81748 KB Output is correct
12 Correct 39 ms 81740 KB Output is correct
13 Correct 46 ms 81748 KB Output is correct
14 Correct 40 ms 81692 KB Output is correct
15 Correct 45 ms 81740 KB Output is correct
16 Correct 43 ms 81724 KB Output is correct
17 Correct 41 ms 81752 KB Output is correct
18 Correct 47 ms 81664 KB Output is correct
19 Correct 39 ms 81736 KB Output is correct
20 Correct 42 ms 81740 KB Output is correct
21 Correct 36 ms 81692 KB Output is correct
22 Correct 189 ms 90884 KB Output is correct
23 Correct 185 ms 89920 KB Output is correct
24 Correct 199 ms 90952 KB Output is correct
25 Correct 205 ms 90068 KB Output is correct
26 Correct 188 ms 87016 KB Output is correct
27 Correct 158 ms 85196 KB Output is correct
28 Correct 167 ms 86980 KB Output is correct
29 Correct 167 ms 85336 KB Output is correct
30 Correct 178 ms 86532 KB Output is correct
31 Correct 169 ms 86360 KB Output is correct
32 Correct 161 ms 86508 KB Output is correct
33 Correct 158 ms 86624 KB Output is correct
34 Correct 178 ms 89148 KB Output is correct
35 Correct 182 ms 89204 KB Output is correct
36 Correct 252 ms 91936 KB Output is correct
37 Correct 243 ms 90256 KB Output is correct
38 Correct 243 ms 89288 KB Output is correct
39 Correct 227 ms 91968 KB Output is correct
40 Correct 236 ms 89160 KB Output is correct
41 Correct 197 ms 86992 KB Output is correct
42 Correct 193 ms 86916 KB Output is correct
43 Correct 203 ms 85348 KB Output is correct
44 Correct 224 ms 85324 KB Output is correct
45 Correct 234 ms 87344 KB Output is correct
46 Correct 225 ms 86732 KB Output is correct
47 Correct 202 ms 84740 KB Output is correct
48 Correct 182 ms 86536 KB Output is correct
49 Correct 200 ms 86484 KB Output is correct
50 Correct 196 ms 89220 KB Output is correct
51 Correct 219 ms 89164 KB Output is correct
52 Correct 209 ms 89168 KB Output is correct
53 Correct 39 ms 81612 KB Output is correct
54 Execution timed out 4033 ms 90668 KB Time limit exceeded
55 Halted 0 ms 0 KB -