oj.uz

Submission #737980

# Submission time Handle Problem Language Result Execution time Memory
737980 2023-05-08T03:33:43 Z resting Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 57972 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;
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);
        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) {
    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();
}

Compilation message

fish2.cpp: In function 'void clear(int)':
fish2.cpp:168:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  168 |         auto [l, r] = x;
      |              ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53476 KB Output is correct
2 Correct 24 ms 53460 KB Output is correct
3 Correct 23 ms 53464 KB Output is correct
4 Correct 23 ms 53448 KB Output is correct
5 Correct 29 ms 53468 KB Output is correct
6 Correct 38 ms 53552 KB Output is correct
7 Correct 30 ms 53440 KB Output is correct
8 Correct 36 ms 53556 KB Output is correct
9 Correct 34 ms 53460 KB Output is correct
10 Correct 31 ms 53452 KB Output is correct
11 Correct 29 ms 53540 KB Output is correct
12 Correct 28 ms 53564 KB Output is correct
13 Correct 33 ms 53532 KB Output is correct
14 Correct 35 ms 53460 KB Output is correct
15 Correct 34 ms 53528 KB Output is correct
16 Correct 30 ms 53544 KB Output is correct
17 Correct 31 ms 53628 KB Output is correct
18 Correct 32 ms 53544 KB Output is correct
19 Correct 27 ms 53460 KB Output is correct
20 Correct 29 ms 53460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 53448 KB Output is correct
2 Correct 171 ms 55756 KB Output is correct
3 Correct 171 ms 56024 KB Output is correct
4 Correct 180 ms 55912 KB Output is correct
5 Correct 170 ms 55944 KB Output is correct
6 Correct 145 ms 55920 KB Output is correct
7 Correct 140 ms 55416 KB Output is correct
8 Correct 154 ms 55868 KB Output is correct
9 Correct 142 ms 55384 KB Output is correct
10 Correct 167 ms 55188 KB Output is correct
11 Correct 153 ms 55304 KB Output is correct
12 Correct 140 ms 55776 KB Output is correct
13 Correct 139 ms 55968 KB Output is correct
14 Correct 171 ms 56364 KB Output is correct
15 Correct 163 ms 56140 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53476 KB Output is correct
2 Correct 24 ms 53460 KB Output is correct
3 Correct 23 ms 53464 KB Output is correct
4 Correct 23 ms 53448 KB Output is correct
5 Correct 29 ms 53468 KB Output is correct
6 Correct 38 ms 53552 KB Output is correct
7 Correct 30 ms 53440 KB Output is correct
8 Correct 36 ms 53556 KB Output is correct
9 Correct 34 ms 53460 KB Output is correct
10 Correct 31 ms 53452 KB Output is correct
11 Correct 29 ms 53540 KB Output is correct
12 Correct 28 ms 53564 KB Output is correct
13 Correct 33 ms 53532 KB Output is correct
14 Correct 35 ms 53460 KB Output is correct
15 Correct 34 ms 53528 KB Output is correct
16 Correct 30 ms 53544 KB Output is correct
17 Correct 31 ms 53628 KB Output is correct
18 Correct 32 ms 53544 KB Output is correct
19 Correct 27 ms 53460 KB Output is correct
20 Correct 29 ms 53460 KB Output is correct
21 Correct 26 ms 53448 KB Output is correct
22 Correct 171 ms 55756 KB Output is correct
23 Correct 171 ms 56024 KB Output is correct
24 Correct 180 ms 55912 KB Output is correct
25 Correct 170 ms 55944 KB Output is correct
26 Correct 145 ms 55920 KB Output is correct
27 Correct 140 ms 55416 KB Output is correct
28 Correct 154 ms 55868 KB Output is correct
29 Correct 142 ms 55384 KB Output is correct
30 Correct 167 ms 55188 KB Output is correct
31 Correct 153 ms 55304 KB Output is correct
32 Correct 140 ms 55776 KB Output is correct
33 Correct 139 ms 55968 KB Output is correct
34 Correct 171 ms 56364 KB Output is correct
35 Correct 163 ms 56140 KB Output is correct
36 Correct 215 ms 55992 KB Output is correct
37 Correct 211 ms 55944 KB Output is correct
38 Correct 256 ms 55964 KB Output is correct
39 Correct 203 ms 55944 KB Output is correct
40 Correct 203 ms 55864 KB Output is correct
41 Correct 157 ms 55972 KB Output is correct
42 Correct 162 ms 55940 KB Output is correct
43 Correct 176 ms 55488 KB Output is correct
44 Correct 178 ms 55492 KB Output is correct
45 Correct 193 ms 55532 KB Output is correct
46 Correct 177 ms 55216 KB Output is correct
47 Correct 177 ms 55116 KB Output is correct
48 Correct 158 ms 55832 KB Output is correct
49 Correct 171 ms 55844 KB Output is correct
50 Correct 174 ms 56560 KB Output is correct
51 Correct 173 ms 56196 KB Output is correct
52 Correct 185 ms 56504 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 53448 KB Output is correct
2 Correct 171 ms 55756 KB Output is correct
3 Correct 171 ms 56024 KB Output is correct
4 Correct 180 ms 55912 KB Output is correct
5 Correct 170 ms 55944 KB Output is correct
6 Correct 145 ms 55920 KB Output is correct
7 Correct 140 ms 55416 KB Output is correct
8 Correct 154 ms 55868 KB Output is correct
9 Correct 142 ms 55384 KB Output is correct
10 Correct 167 ms 55188 KB Output is correct
11 Correct 153 ms 55304 KB Output is correct
12 Correct 140 ms 55776 KB Output is correct
13 Correct 139 ms 55968 KB Output is correct
14 Correct 171 ms 56364 KB Output is correct
15 Correct 163 ms 56140 KB Output is correct
16 Correct 24 ms 53432 KB Output is correct
17 Execution timed out 4075 ms 57148 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 53448 KB Output is correct
2 Correct 171 ms 55756 KB Output is correct
3 Correct 171 ms 56024 KB Output is correct
4 Correct 180 ms 55912 KB Output is correct
5 Correct 170 ms 55944 KB Output is correct
6 Correct 145 ms 55920 KB Output is correct
7 Correct 140 ms 55416 KB Output is correct
8 Correct 154 ms 55868 KB Output is correct
9 Correct 142 ms 55384 KB Output is correct
10 Correct 167 ms 55188 KB Output is correct
11 Correct 153 ms 55304 KB Output is correct
12 Correct 140 ms 55776 KB Output is correct
13 Correct 139 ms 55968 KB Output is correct
14 Correct 171 ms 56364 KB Output is correct
15 Correct 163 ms 56140 KB Output is correct
16 Correct 26 ms 53528 KB Output is correct
17 Correct 1100 ms 56168 KB Output is correct
18 Correct 1155 ms 57900 KB Output is correct
19 Correct 1779 ms 56292 KB Output is correct
20 Correct 1274 ms 57872 KB Output is correct
21 Correct 1350 ms 56236 KB Output is correct
22 Correct 1182 ms 57964 KB Output is correct
23 Correct 1459 ms 56128 KB Output is correct
24 Correct 1192 ms 57972 KB Output is correct
25 Correct 1540 ms 56196 KB Output is correct
26 Correct 876 ms 56668 KB Output is correct
27 Correct 769 ms 56728 KB Output is correct
28 Correct 1045 ms 57020 KB Output is correct
29 Correct 805 ms 56824 KB Output is correct
30 Correct 747 ms 56652 KB Output is correct
31 Correct 1057 ms 56984 KB Output is correct
32 Correct 1118 ms 57264 KB Output is correct
33 Correct 845 ms 55716 KB Output is correct
34 Correct 1128 ms 57624 KB Output is correct
35 Correct 944 ms 55488 KB Output is correct
36 Correct 1101 ms 57348 KB Output is correct
37 Correct 1219 ms 56896 KB Output is correct
38 Correct 1247 ms 56728 KB Output is correct
39 Correct 929 ms 57276 KB Output is correct
40 Correct 1022 ms 57080 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53476 KB Output is correct
2 Correct 24 ms 53460 KB Output is correct
3 Correct 23 ms 53464 KB Output is correct
4 Correct 23 ms 53448 KB Output is correct
5 Correct 29 ms 53468 KB Output is correct
6 Correct 38 ms 53552 KB Output is correct
7 Correct 30 ms 53440 KB Output is correct
8 Correct 36 ms 53556 KB Output is correct
9 Correct 34 ms 53460 KB Output is correct
10 Correct 31 ms 53452 KB Output is correct
11 Correct 29 ms 53540 KB Output is correct
12 Correct 28 ms 53564 KB Output is correct
13 Correct 33 ms 53532 KB Output is correct
14 Correct 35 ms 53460 KB Output is correct
15 Correct 34 ms 53528 KB Output is correct
16 Correct 30 ms 53544 KB Output is correct
17 Correct 31 ms 53628 KB Output is correct
18 Correct 32 ms 53544 KB Output is correct
19 Correct 27 ms 53460 KB Output is correct
20 Correct 29 ms 53460 KB Output is correct
21 Correct 26 ms 53448 KB Output is correct
22 Correct 171 ms 55756 KB Output is correct
23 Correct 171 ms 56024 KB Output is correct
24 Correct 180 ms 55912 KB Output is correct
25 Correct 170 ms 55944 KB Output is correct
26 Correct 145 ms 55920 KB Output is correct
27 Correct 140 ms 55416 KB Output is correct
28 Correct 154 ms 55868 KB Output is correct
29 Correct 142 ms 55384 KB Output is correct
30 Correct 167 ms 55188 KB Output is correct
31 Correct 153 ms 55304 KB Output is correct
32 Correct 140 ms 55776 KB Output is correct
33 Correct 139 ms 55968 KB Output is correct
34 Correct 171 ms 56364 KB Output is correct
35 Correct 163 ms 56140 KB Output is correct
36 Correct 215 ms 55992 KB Output is correct
37 Correct 211 ms 55944 KB Output is correct
38 Correct 256 ms 55964 KB Output is correct
39 Correct 203 ms 55944 KB Output is correct
40 Correct 203 ms 55864 KB Output is correct
41 Correct 157 ms 55972 KB Output is correct
42 Correct 162 ms 55940 KB Output is correct
43 Correct 176 ms 55488 KB Output is correct
44 Correct 178 ms 55492 KB Output is correct
45 Correct 193 ms 55532 KB Output is correct
46 Correct 177 ms 55216 KB Output is correct
47 Correct 177 ms 55116 KB Output is correct
48 Correct 158 ms 55832 KB Output is correct
49 Correct 171 ms 55844 KB Output is correct
50 Correct 174 ms 56560 KB Output is correct
51 Correct 173 ms 56196 KB Output is correct
52 Correct 185 ms 56504 KB Output is correct
53 Correct 24 ms 53432 KB Output is correct
54 Execution timed out 4075 ms 57148 KB Time limit exceeded
55 Halted 0 ms 0 KB -