oj.uz

Submission #737943

# Submission time Handle Problem Language Result Execution time Memory
737943 2023-05-08T02:49:37 Z resting Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 92236 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 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) {
        ll 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, ll 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<ll>(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 36 ms 81616 KB Output is correct
2 Correct 37 ms 81684 KB Output is correct
3 Correct 39 ms 81712 KB Output is correct
4 Correct 36 ms 81696 KB Output is correct
5 Correct 44 ms 81684 KB Output is correct
6 Correct 58 ms 81680 KB Output is correct
7 Correct 47 ms 81724 KB Output is correct
8 Correct 72 ms 81724 KB Output is correct
9 Correct 57 ms 81820 KB Output is correct
10 Correct 40 ms 81720 KB Output is correct
11 Correct 45 ms 81720 KB Output is correct
12 Correct 42 ms 81708 KB Output is correct
13 Correct 57 ms 81644 KB Output is correct
14 Correct 42 ms 81708 KB Output is correct
15 Correct 50 ms 81748 KB Output is correct
16 Correct 49 ms 81744 KB Output is correct
17 Correct 43 ms 81672 KB Output is correct
18 Correct 52 ms 81752 KB Output is correct
19 Correct 44 ms 81752 KB Output is correct
20 Correct 46 ms 81672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 81612 KB Output is correct
2 Correct 239 ms 90940 KB Output is correct
3 Correct 233 ms 90132 KB Output is correct
4 Correct 238 ms 91048 KB Output is correct
5 Correct 235 ms 90192 KB Output is correct
6 Correct 190 ms 87108 KB Output is correct
7 Correct 183 ms 85504 KB Output is correct
8 Correct 196 ms 87240 KB Output is correct
9 Correct 186 ms 85384 KB Output is correct
10 Correct 205 ms 86788 KB Output is correct
11 Correct 189 ms 86484 KB Output is correct
12 Correct 189 ms 86732 KB Output is correct
13 Correct 189 ms 86584 KB Output is correct
14 Correct 209 ms 89292 KB Output is correct
15 Correct 217 ms 89200 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81616 KB Output is correct
2 Correct 37 ms 81684 KB Output is correct
3 Correct 39 ms 81712 KB Output is correct
4 Correct 36 ms 81696 KB Output is correct
5 Correct 44 ms 81684 KB Output is correct
6 Correct 58 ms 81680 KB Output is correct
7 Correct 47 ms 81724 KB Output is correct
8 Correct 72 ms 81724 KB Output is correct
9 Correct 57 ms 81820 KB Output is correct
10 Correct 40 ms 81720 KB Output is correct
11 Correct 45 ms 81720 KB Output is correct
12 Correct 42 ms 81708 KB Output is correct
13 Correct 57 ms 81644 KB Output is correct
14 Correct 42 ms 81708 KB Output is correct
15 Correct 50 ms 81748 KB Output is correct
16 Correct 49 ms 81744 KB Output is correct
17 Correct 43 ms 81672 KB Output is correct
18 Correct 52 ms 81752 KB Output is correct
19 Correct 44 ms 81752 KB Output is correct
20 Correct 46 ms 81672 KB Output is correct
21 Correct 39 ms 81612 KB Output is correct
22 Correct 239 ms 90940 KB Output is correct
23 Correct 233 ms 90132 KB Output is correct
24 Correct 238 ms 91048 KB Output is correct
25 Correct 235 ms 90192 KB Output is correct
26 Correct 190 ms 87108 KB Output is correct
27 Correct 183 ms 85504 KB Output is correct
28 Correct 196 ms 87240 KB Output is correct
29 Correct 186 ms 85384 KB Output is correct
30 Correct 205 ms 86788 KB Output is correct
31 Correct 189 ms 86484 KB Output is correct
32 Correct 189 ms 86732 KB Output is correct
33 Correct 189 ms 86584 KB Output is correct
34 Correct 209 ms 89292 KB Output is correct
35 Correct 217 ms 89200 KB Output is correct
36 Correct 302 ms 92108 KB Output is correct
37 Correct 322 ms 90444 KB Output is correct
38 Correct 326 ms 89460 KB Output is correct
39 Correct 277 ms 92236 KB Output is correct
40 Correct 333 ms 89428 KB Output is correct
41 Correct 213 ms 87184 KB Output is correct
42 Correct 217 ms 87268 KB Output is correct
43 Correct 260 ms 85460 KB Output is correct
44 Correct 281 ms 85548 KB Output is correct
45 Correct 292 ms 87468 KB Output is correct
46 Correct 262 ms 86876 KB Output is correct
47 Correct 269 ms 84820 KB Output is correct
48 Correct 220 ms 86724 KB Output is correct
49 Correct 237 ms 86592 KB Output is correct
50 Correct 236 ms 89292 KB Output is correct
51 Correct 243 ms 89168 KB Output is correct
52 Correct 247 ms 89392 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 81612 KB Output is correct
2 Correct 239 ms 90940 KB Output is correct
3 Correct 233 ms 90132 KB Output is correct
4 Correct 238 ms 91048 KB Output is correct
5 Correct 235 ms 90192 KB Output is correct
6 Correct 190 ms 87108 KB Output is correct
7 Correct 183 ms 85504 KB Output is correct
8 Correct 196 ms 87240 KB Output is correct
9 Correct 186 ms 85384 KB Output is correct
10 Correct 205 ms 86788 KB Output is correct
11 Correct 189 ms 86484 KB Output is correct
12 Correct 189 ms 86732 KB Output is correct
13 Correct 189 ms 86584 KB Output is correct
14 Correct 209 ms 89292 KB Output is correct
15 Correct 217 ms 89200 KB Output is correct
16 Correct 42 ms 81692 KB Output is correct
17 Execution timed out 4035 ms 90592 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 81612 KB Output is correct
2 Correct 239 ms 90940 KB Output is correct
3 Correct 233 ms 90132 KB Output is correct
4 Correct 238 ms 91048 KB Output is correct
5 Correct 235 ms 90192 KB Output is correct
6 Correct 190 ms 87108 KB Output is correct
7 Correct 183 ms 85504 KB Output is correct
8 Correct 196 ms 87240 KB Output is correct
9 Correct 186 ms 85384 KB Output is correct
10 Correct 205 ms 86788 KB Output is correct
11 Correct 189 ms 86484 KB Output is correct
12 Correct 189 ms 86732 KB Output is correct
13 Correct 189 ms 86584 KB Output is correct
14 Correct 209 ms 89292 KB Output is correct
15 Correct 217 ms 89200 KB Output is correct
16 Correct 37 ms 81620 KB Output is correct
17 Correct 1541 ms 91424 KB Output is correct
18 Correct 1559 ms 91140 KB Output is correct
19 Correct 2279 ms 90676 KB Output is correct
20 Correct 1575 ms 91580 KB Output is correct
21 Correct 2774 ms 91196 KB Output is correct
22 Correct 1586 ms 91236 KB Output is correct
23 Correct 2360 ms 90672 KB Output is correct
24 Correct 1614 ms 91172 KB Output is correct
25 Correct 2303 ms 90404 KB Output is correct
26 Correct 937 ms 87496 KB Output is correct
27 Correct 944 ms 87168 KB Output is correct
28 Correct 1350 ms 88896 KB Output is correct
29 Correct 936 ms 87192 KB Output is correct
30 Correct 929 ms 87300 KB Output is correct
31 Correct 1399 ms 88992 KB Output is correct
32 Correct 1465 ms 89532 KB Output is correct
33 Correct 1157 ms 86692 KB Output is correct
34 Correct 1434 ms 90612 KB Output is correct
35 Correct 1275 ms 86692 KB Output is correct
36 Correct 1432 ms 89312 KB Output is correct
37 Correct 1598 ms 89056 KB Output is correct
38 Correct 1486 ms 88596 KB Output is correct
39 Correct 1126 ms 89704 KB Output is correct
40 Correct 1041 ms 89576 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81616 KB Output is correct
2 Correct 37 ms 81684 KB Output is correct
3 Correct 39 ms 81712 KB Output is correct
4 Correct 36 ms 81696 KB Output is correct
5 Correct 44 ms 81684 KB Output is correct
6 Correct 58 ms 81680 KB Output is correct
7 Correct 47 ms 81724 KB Output is correct
8 Correct 72 ms 81724 KB Output is correct
9 Correct 57 ms 81820 KB Output is correct
10 Correct 40 ms 81720 KB Output is correct
11 Correct 45 ms 81720 KB Output is correct
12 Correct 42 ms 81708 KB Output is correct
13 Correct 57 ms 81644 KB Output is correct
14 Correct 42 ms 81708 KB Output is correct
15 Correct 50 ms 81748 KB Output is correct
16 Correct 49 ms 81744 KB Output is correct
17 Correct 43 ms 81672 KB Output is correct
18 Correct 52 ms 81752 KB Output is correct
19 Correct 44 ms 81752 KB Output is correct
20 Correct 46 ms 81672 KB Output is correct
21 Correct 39 ms 81612 KB Output is correct
22 Correct 239 ms 90940 KB Output is correct
23 Correct 233 ms 90132 KB Output is correct
24 Correct 238 ms 91048 KB Output is correct
25 Correct 235 ms 90192 KB Output is correct
26 Correct 190 ms 87108 KB Output is correct
27 Correct 183 ms 85504 KB Output is correct
28 Correct 196 ms 87240 KB Output is correct
29 Correct 186 ms 85384 KB Output is correct
30 Correct 205 ms 86788 KB Output is correct
31 Correct 189 ms 86484 KB Output is correct
32 Correct 189 ms 86732 KB Output is correct
33 Correct 189 ms 86584 KB Output is correct
34 Correct 209 ms 89292 KB Output is correct
35 Correct 217 ms 89200 KB Output is correct
36 Correct 302 ms 92108 KB Output is correct
37 Correct 322 ms 90444 KB Output is correct
38 Correct 326 ms 89460 KB Output is correct
39 Correct 277 ms 92236 KB Output is correct
40 Correct 333 ms 89428 KB Output is correct
41 Correct 213 ms 87184 KB Output is correct
42 Correct 217 ms 87268 KB Output is correct
43 Correct 260 ms 85460 KB Output is correct
44 Correct 281 ms 85548 KB Output is correct
45 Correct 292 ms 87468 KB Output is correct
46 Correct 262 ms 86876 KB Output is correct
47 Correct 269 ms 84820 KB Output is correct
48 Correct 220 ms 86724 KB Output is correct
49 Correct 237 ms 86592 KB Output is correct
50 Correct 236 ms 89292 KB Output is correct
51 Correct 243 ms 89168 KB Output is correct
52 Correct 247 ms 89392 KB Output is correct
53 Correct 42 ms 81692 KB Output is correct
54 Execution timed out 4035 ms 90592 KB Time limit exceeded
55 Halted 0 ms 0 KB -