oj.uz

Submission #737936

# Submission time Handle Problem Language Result Execution time Memory
737936 2023-05-08T02:44:06 Z resting Fish 2 (JOI22_fish2) C++17
60 / 100
 4000 ms 112056 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() {
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97244 KB Output is correct
2 Correct 41 ms 97280 KB Output is correct
3 Correct 48 ms 97256 KB Output is correct
4 Correct 44 ms 97336 KB Output is correct
5 Correct 50 ms 97336 KB Output is correct
6 Correct 64 ms 97312 KB Output is correct
7 Correct 53 ms 97356 KB Output is correct
8 Correct 78 ms 97352 KB Output is correct
9 Correct 69 ms 97364 KB Output is correct
10 Correct 48 ms 97356 KB Output is correct
11 Correct 53 ms 97356 KB Output is correct
12 Correct 48 ms 97328 KB Output is correct
13 Correct 59 ms 97396 KB Output is correct
14 Correct 48 ms 97384 KB Output is correct
15 Correct 52 ms 97348 KB Output is correct
16 Correct 54 ms 97352 KB Output is correct
17 Correct 48 ms 97356 KB Output is correct
18 Correct 57 ms 97400 KB Output is correct
19 Correct 51 ms 97356 KB Output is correct
20 Correct 57 ms 97352 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97352 KB Output is correct
2 Correct 283 ms 109536 KB Output is correct
3 Correct 272 ms 108324 KB Output is correct
4 Correct 265 ms 109644 KB Output is correct
5 Correct 249 ms 108460 KB Output is correct
6 Correct 232 ms 104288 KB Output is correct
7 Correct 228 ms 102224 KB Output is correct
8 Correct 242 ms 104404 KB Output is correct
9 Correct 241 ms 102120 KB Output is correct
10 Correct 244 ms 103796 KB Output is correct
11 Correct 226 ms 103500 KB Output is correct
12 Correct 223 ms 103732 KB Output is correct
13 Correct 232 ms 103740 KB Output is correct
14 Correct 254 ms 107296 KB Output is correct
15 Correct 245 ms 107128 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97244 KB Output is correct
2 Correct 41 ms 97280 KB Output is correct
3 Correct 48 ms 97256 KB Output is correct
4 Correct 44 ms 97336 KB Output is correct
5 Correct 50 ms 97336 KB Output is correct
6 Correct 64 ms 97312 KB Output is correct
7 Correct 53 ms 97356 KB Output is correct
8 Correct 78 ms 97352 KB Output is correct
9 Correct 69 ms 97364 KB Output is correct
10 Correct 48 ms 97356 KB Output is correct
11 Correct 53 ms 97356 KB Output is correct
12 Correct 48 ms 97328 KB Output is correct
13 Correct 59 ms 97396 KB Output is correct
14 Correct 48 ms 97384 KB Output is correct
15 Correct 52 ms 97348 KB Output is correct
16 Correct 54 ms 97352 KB Output is correct
17 Correct 48 ms 97356 KB Output is correct
18 Correct 57 ms 97400 KB Output is correct
19 Correct 51 ms 97356 KB Output is correct
20 Correct 57 ms 97352 KB Output is correct
21 Correct 43 ms 97352 KB Output is correct
22 Correct 283 ms 109536 KB Output is correct
23 Correct 272 ms 108324 KB Output is correct
24 Correct 265 ms 109644 KB Output is correct
25 Correct 249 ms 108460 KB Output is correct
26 Correct 232 ms 104288 KB Output is correct
27 Correct 228 ms 102224 KB Output is correct
28 Correct 242 ms 104404 KB Output is correct
29 Correct 241 ms 102120 KB Output is correct
30 Correct 244 ms 103796 KB Output is correct
31 Correct 226 ms 103500 KB Output is correct
32 Correct 223 ms 103732 KB Output is correct
33 Correct 232 ms 103740 KB Output is correct
34 Correct 254 ms 107296 KB Output is correct
35 Correct 245 ms 107128 KB Output is correct
36 Correct 347 ms 111680 KB Output is correct
37 Correct 375 ms 109304 KB Output is correct
38 Correct 370 ms 107748 KB Output is correct
39 Correct 317 ms 111648 KB Output is correct
40 Correct 365 ms 107724 KB Output is correct
41 Correct 275 ms 105272 KB Output is correct
42 Correct 264 ms 105328 KB Output is correct
43 Correct 331 ms 102472 KB Output is correct
44 Correct 300 ms 102392 KB Output is correct
45 Correct 339 ms 105436 KB Output is correct
46 Correct 288 ms 104640 KB Output is correct
47 Correct 298 ms 101656 KB Output is correct
48 Correct 251 ms 104084 KB Output is correct
49 Correct 294 ms 104140 KB Output is correct
50 Correct 277 ms 107932 KB Output is correct
51 Correct 295 ms 107816 KB Output is correct
52 Correct 281 ms 107980 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97352 KB Output is correct
2 Correct 283 ms 109536 KB Output is correct
3 Correct 272 ms 108324 KB Output is correct
4 Correct 265 ms 109644 KB Output is correct
5 Correct 249 ms 108460 KB Output is correct
6 Correct 232 ms 104288 KB Output is correct
7 Correct 228 ms 102224 KB Output is correct
8 Correct 242 ms 104404 KB Output is correct
9 Correct 241 ms 102120 KB Output is correct
10 Correct 244 ms 103796 KB Output is correct
11 Correct 226 ms 103500 KB Output is correct
12 Correct 223 ms 103732 KB Output is correct
13 Correct 232 ms 103740 KB Output is correct
14 Correct 254 ms 107296 KB Output is correct
15 Correct 245 ms 107128 KB Output is correct
16 Correct 41 ms 97228 KB Output is correct
17 Execution timed out 4069 ms 109512 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97352 KB Output is correct
2 Correct 283 ms 109536 KB Output is correct
3 Correct 272 ms 108324 KB Output is correct
4 Correct 265 ms 109644 KB Output is correct
5 Correct 249 ms 108460 KB Output is correct
6 Correct 232 ms 104288 KB Output is correct
7 Correct 228 ms 102224 KB Output is correct
8 Correct 242 ms 104404 KB Output is correct
9 Correct 241 ms 102120 KB Output is correct
10 Correct 244 ms 103796 KB Output is correct
11 Correct 226 ms 103500 KB Output is correct
12 Correct 223 ms 103732 KB Output is correct
13 Correct 232 ms 103740 KB Output is correct
14 Correct 254 ms 107296 KB Output is correct
15 Correct 245 ms 107128 KB Output is correct
16 Correct 47 ms 97228 KB Output is correct
17 Correct 1685 ms 111196 KB Output is correct
18 Correct 1687 ms 111844 KB Output is correct
19 Correct 2430 ms 110136 KB Output is correct
20 Correct 1739 ms 112048 KB Output is correct
21 Correct 2954 ms 111252 KB Output is correct
22 Correct 1782 ms 111820 KB Output is correct
23 Correct 2521 ms 110444 KB Output is correct
24 Correct 1738 ms 112056 KB Output is correct
25 Correct 2471 ms 110064 KB Output is correct
26 Correct 1076 ms 107260 KB Output is correct
27 Correct 1081 ms 107152 KB Output is correct
28 Correct 1470 ms 108664 KB Output is correct
29 Correct 1085 ms 107288 KB Output is correct
30 Correct 1072 ms 107212 KB Output is correct
31 Correct 1505 ms 108680 KB Output is correct
32 Correct 1611 ms 109852 KB Output is correct
33 Correct 1327 ms 105076 KB Output is correct
34 Correct 1621 ms 111164 KB Output is correct
35 Correct 1410 ms 105928 KB Output is correct
36 Correct 1586 ms 109248 KB Output is correct
37 Correct 1753 ms 108624 KB Output is correct
38 Correct 1648 ms 107960 KB Output is correct
39 Correct 1296 ms 109660 KB Output is correct
40 Correct 1234 ms 109528 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 97244 KB Output is correct
2 Correct 41 ms 97280 KB Output is correct
3 Correct 48 ms 97256 KB Output is correct
4 Correct 44 ms 97336 KB Output is correct
5 Correct 50 ms 97336 KB Output is correct
6 Correct 64 ms 97312 KB Output is correct
7 Correct 53 ms 97356 KB Output is correct
8 Correct 78 ms 97352 KB Output is correct
9 Correct 69 ms 97364 KB Output is correct
10 Correct 48 ms 97356 KB Output is correct
11 Correct 53 ms 97356 KB Output is correct
12 Correct 48 ms 97328 KB Output is correct
13 Correct 59 ms 97396 KB Output is correct
14 Correct 48 ms 97384 KB Output is correct
15 Correct 52 ms 97348 KB Output is correct
16 Correct 54 ms 97352 KB Output is correct
17 Correct 48 ms 97356 KB Output is correct
18 Correct 57 ms 97400 KB Output is correct
19 Correct 51 ms 97356 KB Output is correct
20 Correct 57 ms 97352 KB Output is correct
21 Correct 43 ms 97352 KB Output is correct
22 Correct 283 ms 109536 KB Output is correct
23 Correct 272 ms 108324 KB Output is correct
24 Correct 265 ms 109644 KB Output is correct
25 Correct 249 ms 108460 KB Output is correct
26 Correct 232 ms 104288 KB Output is correct
27 Correct 228 ms 102224 KB Output is correct
28 Correct 242 ms 104404 KB Output is correct
29 Correct 241 ms 102120 KB Output is correct
30 Correct 244 ms 103796 KB Output is correct
31 Correct 226 ms 103500 KB Output is correct
32 Correct 223 ms 103732 KB Output is correct
33 Correct 232 ms 103740 KB Output is correct
34 Correct 254 ms 107296 KB Output is correct
35 Correct 245 ms 107128 KB Output is correct
36 Correct 347 ms 111680 KB Output is correct
37 Correct 375 ms 109304 KB Output is correct
38 Correct 370 ms 107748 KB Output is correct
39 Correct 317 ms 111648 KB Output is correct
40 Correct 365 ms 107724 KB Output is correct
41 Correct 275 ms 105272 KB Output is correct
42 Correct 264 ms 105328 KB Output is correct
43 Correct 331 ms 102472 KB Output is correct
44 Correct 300 ms 102392 KB Output is correct
45 Correct 339 ms 105436 KB Output is correct
46 Correct 288 ms 104640 KB Output is correct
47 Correct 298 ms 101656 KB Output is correct
48 Correct 251 ms 104084 KB Output is correct
49 Correct 294 ms 104140 KB Output is correct
50 Correct 277 ms 107932 KB Output is correct
51 Correct 295 ms 107816 KB Output is correct
52 Correct 281 ms 107980 KB Output is correct
53 Correct 41 ms 97228 KB Output is correct
54 Execution timed out 4069 ms 109512 KB Time limit exceeded
55 Halted 0 ms 0 KB -