oj.uz

Submission #737937

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

#define int long long

const int mx = 1e5 + 5;
const int 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, 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, int 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, int 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, int 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;
    }
    int 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<int> ac4;
int n;
void redo(int i) {
    //cout << "REDO " << i << endl;
    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);
    }
    //walking time
    int l = i, r = i;
    while (1) {
        int t = ac3.qsum(l, r);
        int wr = ac3.walkl(r + 1, t);
        int wl = ac3.walkr(l - 1, t);
        //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]) r++;
        else l--;
    }
}

void upd(int i, int v) {
    ac4[i] = v; ac3.upd(i, v);
    redo(i);
    if (i < n + 1)redo(i + 1);
    if (i)redo(i - 1);
}

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<int>(n + 2, 0);
    for (int i = 0; i <= n + 1; i++) upd(i, a[i]);
    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);
        } else {
            int l, r; cin >> l >> r;
            upd(l - 1, inf); upd(r + 1, inf);
            cout << (r - l + 1 - ac2.q(l, r)) << endl;
            upd(l - 1, a[l - 1]); upd(r + 1, a[r + 1]);
        }
    }
}

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 40 ms 97376 KB Output is correct
2 Correct 44 ms 97312 KB Output is correct
3 Correct 43 ms 97288 KB Output is correct
4 Correct 48 ms 97364 KB Output is correct
5 Correct 48 ms 97364 KB Output is correct
6 Correct 63 ms 97312 KB Output is correct
7 Correct 50 ms 97412 KB Output is correct
8 Correct 76 ms 97416 KB Output is correct
9 Correct 66 ms 97348 KB Output is correct
10 Correct 45 ms 97356 KB Output is correct
11 Correct 48 ms 97400 KB Output is correct
12 Correct 46 ms 97420 KB Output is correct
13 Correct 61 ms 97412 KB Output is correct
14 Correct 46 ms 97376 KB Output is correct
15 Correct 58 ms 97320 KB Output is correct
16 Correct 54 ms 97404 KB Output is correct
17 Correct 48 ms 97352 KB Output is correct
18 Correct 56 ms 97424 KB Output is correct
19 Correct 48 ms 97376 KB Output is correct
20 Correct 50 ms 97348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97328 KB Output is correct
2 Correct 258 ms 109688 KB Output is correct
3 Correct 239 ms 108408 KB Output is correct
4 Correct 244 ms 109576 KB Output is correct
5 Correct 242 ms 108600 KB Output is correct
6 Correct 216 ms 104404 KB Output is correct
7 Correct 237 ms 102068 KB Output is correct
8 Correct 213 ms 104504 KB Output is correct
9 Correct 225 ms 102116 KB Output is correct
10 Correct 225 ms 103884 KB Output is correct
11 Correct 217 ms 103592 KB Output is correct
12 Correct 200 ms 103828 KB Output is correct
13 Correct 215 ms 103824 KB Output is correct
14 Correct 245 ms 107392 KB Output is correct
15 Correct 240 ms 107220 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97376 KB Output is correct
2 Correct 44 ms 97312 KB Output is correct
3 Correct 43 ms 97288 KB Output is correct
4 Correct 48 ms 97364 KB Output is correct
5 Correct 48 ms 97364 KB Output is correct
6 Correct 63 ms 97312 KB Output is correct
7 Correct 50 ms 97412 KB Output is correct
8 Correct 76 ms 97416 KB Output is correct
9 Correct 66 ms 97348 KB Output is correct
10 Correct 45 ms 97356 KB Output is correct
11 Correct 48 ms 97400 KB Output is correct
12 Correct 46 ms 97420 KB Output is correct
13 Correct 61 ms 97412 KB Output is correct
14 Correct 46 ms 97376 KB Output is correct
15 Correct 58 ms 97320 KB Output is correct
16 Correct 54 ms 97404 KB Output is correct
17 Correct 48 ms 97352 KB Output is correct
18 Correct 56 ms 97424 KB Output is correct
19 Correct 48 ms 97376 KB Output is correct
20 Correct 50 ms 97348 KB Output is correct
21 Correct 40 ms 97328 KB Output is correct
22 Correct 258 ms 109688 KB Output is correct
23 Correct 239 ms 108408 KB Output is correct
24 Correct 244 ms 109576 KB Output is correct
25 Correct 242 ms 108600 KB Output is correct
26 Correct 216 ms 104404 KB Output is correct
27 Correct 237 ms 102068 KB Output is correct
28 Correct 213 ms 104504 KB Output is correct
29 Correct 225 ms 102116 KB Output is correct
30 Correct 225 ms 103884 KB Output is correct
31 Correct 217 ms 103592 KB Output is correct
32 Correct 200 ms 103828 KB Output is correct
33 Correct 215 ms 103824 KB Output is correct
34 Correct 245 ms 107392 KB Output is correct
35 Correct 240 ms 107220 KB Output is correct
36 Correct 355 ms 111072 KB Output is correct
37 Correct 405 ms 108792 KB Output is correct
38 Correct 408 ms 107536 KB Output is correct
39 Correct 347 ms 110980 KB Output is correct
40 Correct 399 ms 107388 KB Output is correct
41 Correct 274 ms 104320 KB Output is correct
42 Correct 260 ms 104368 KB Output is correct
43 Correct 315 ms 102184 KB Output is correct
44 Correct 330 ms 102108 KB Output is correct
45 Correct 313 ms 104900 KB Output is correct
46 Correct 307 ms 104072 KB Output is correct
47 Correct 331 ms 101412 KB Output is correct
48 Correct 269 ms 104052 KB Output is correct
49 Correct 293 ms 103924 KB Output is correct
50 Correct 259 ms 107416 KB Output is correct
51 Correct 299 ms 107216 KB Output is correct
52 Correct 292 ms 107340 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97328 KB Output is correct
2 Correct 258 ms 109688 KB Output is correct
3 Correct 239 ms 108408 KB Output is correct
4 Correct 244 ms 109576 KB Output is correct
5 Correct 242 ms 108600 KB Output is correct
6 Correct 216 ms 104404 KB Output is correct
7 Correct 237 ms 102068 KB Output is correct
8 Correct 213 ms 104504 KB Output is correct
9 Correct 225 ms 102116 KB Output is correct
10 Correct 225 ms 103884 KB Output is correct
11 Correct 217 ms 103592 KB Output is correct
12 Correct 200 ms 103828 KB Output is correct
13 Correct 215 ms 103824 KB Output is correct
14 Correct 245 ms 107392 KB Output is correct
15 Correct 240 ms 107220 KB Output is correct
16 Correct 42 ms 97356 KB Output is correct
17 Execution timed out 4054 ms 108772 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97328 KB Output is correct
2 Correct 258 ms 109688 KB Output is correct
3 Correct 239 ms 108408 KB Output is correct
4 Correct 244 ms 109576 KB Output is correct
5 Correct 242 ms 108600 KB Output is correct
6 Correct 216 ms 104404 KB Output is correct
7 Correct 237 ms 102068 KB Output is correct
8 Correct 213 ms 104504 KB Output is correct
9 Correct 225 ms 102116 KB Output is correct
10 Correct 225 ms 103884 KB Output is correct
11 Correct 217 ms 103592 KB Output is correct
12 Correct 200 ms 103828 KB Output is correct
13 Correct 215 ms 103824 KB Output is correct
14 Correct 245 ms 107392 KB Output is correct
15 Correct 240 ms 107220 KB Output is correct
16 Correct 43 ms 97360 KB Output is correct
17 Correct 1741 ms 109832 KB Output is correct
18 Correct 1723 ms 110216 KB Output is correct
19 Correct 2712 ms 108964 KB Output is correct
20 Correct 1775 ms 110652 KB Output is correct
21 Correct 2936 ms 109960 KB Output is correct
22 Correct 1645 ms 110284 KB Output is correct
23 Correct 2544 ms 109336 KB Output is correct
24 Correct 1749 ms 110168 KB Output is correct
25 Correct 2551 ms 108984 KB Output is correct
26 Correct 974 ms 104996 KB Output is correct
27 Correct 976 ms 104804 KB Output is correct
28 Correct 1394 ms 107424 KB Output is correct
29 Correct 977 ms 104956 KB Output is correct
30 Correct 961 ms 104680 KB Output is correct
31 Correct 1432 ms 107044 KB Output is correct
32 Correct 1558 ms 107944 KB Output is correct
33 Correct 1193 ms 103920 KB Output is correct
34 Correct 1449 ms 109260 KB Output is correct
35 Correct 1296 ms 104388 KB Output is correct
36 Correct 1540 ms 107592 KB Output is correct
37 Correct 1677 ms 107092 KB Output is correct
38 Correct 1551 ms 106696 KB Output is correct
39 Correct 1172 ms 108068 KB Output is correct
40 Correct 1102 ms 107920 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97376 KB Output is correct
2 Correct 44 ms 97312 KB Output is correct
3 Correct 43 ms 97288 KB Output is correct
4 Correct 48 ms 97364 KB Output is correct
5 Correct 48 ms 97364 KB Output is correct
6 Correct 63 ms 97312 KB Output is correct
7 Correct 50 ms 97412 KB Output is correct
8 Correct 76 ms 97416 KB Output is correct
9 Correct 66 ms 97348 KB Output is correct
10 Correct 45 ms 97356 KB Output is correct
11 Correct 48 ms 97400 KB Output is correct
12 Correct 46 ms 97420 KB Output is correct
13 Correct 61 ms 97412 KB Output is correct
14 Correct 46 ms 97376 KB Output is correct
15 Correct 58 ms 97320 KB Output is correct
16 Correct 54 ms 97404 KB Output is correct
17 Correct 48 ms 97352 KB Output is correct
18 Correct 56 ms 97424 KB Output is correct
19 Correct 48 ms 97376 KB Output is correct
20 Correct 50 ms 97348 KB Output is correct
21 Correct 40 ms 97328 KB Output is correct
22 Correct 258 ms 109688 KB Output is correct
23 Correct 239 ms 108408 KB Output is correct
24 Correct 244 ms 109576 KB Output is correct
25 Correct 242 ms 108600 KB Output is correct
26 Correct 216 ms 104404 KB Output is correct
27 Correct 237 ms 102068 KB Output is correct
28 Correct 213 ms 104504 KB Output is correct
29 Correct 225 ms 102116 KB Output is correct
30 Correct 225 ms 103884 KB Output is correct
31 Correct 217 ms 103592 KB Output is correct
32 Correct 200 ms 103828 KB Output is correct
33 Correct 215 ms 103824 KB Output is correct
34 Correct 245 ms 107392 KB Output is correct
35 Correct 240 ms 107220 KB Output is correct
36 Correct 355 ms 111072 KB Output is correct
37 Correct 405 ms 108792 KB Output is correct
38 Correct 408 ms 107536 KB Output is correct
39 Correct 347 ms 110980 KB Output is correct
40 Correct 399 ms 107388 KB Output is correct
41 Correct 274 ms 104320 KB Output is correct
42 Correct 260 ms 104368 KB Output is correct
43 Correct 315 ms 102184 KB Output is correct
44 Correct 330 ms 102108 KB Output is correct
45 Correct 313 ms 104900 KB Output is correct
46 Correct 307 ms 104072 KB Output is correct
47 Correct 331 ms 101412 KB Output is correct
48 Correct 269 ms 104052 KB Output is correct
49 Correct 293 ms 103924 KB Output is correct
50 Correct 259 ms 107416 KB Output is correct
51 Correct 299 ms 107216 KB Output is correct
52 Correct 292 ms 107340 KB Output is correct
53 Correct 42 ms 97356 KB Output is correct
54 Execution timed out 4054 ms 108772 KB Time limit exceeded
55 Halted 0 ms 0 KB -