oj.uz

Submission #737934

# Submission time Handle Problem Language Result Execution time Memory
737934 2023-05-08T02:27:29 Z resting Fish 2 (JOI22_fish2) C++17
8 / 100
 262 ms 110248 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 = lm.rbegin(); t != lm.rend() && t->first >= qi; t++)
                res.push_back(*t);
        }
    }
};
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) {
    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 << 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97228 KB Output is correct
2 Correct 41 ms 97228 KB Output is correct
3 Incorrect 40 ms 97400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97260 KB Output is correct
2 Correct 262 ms 109564 KB Output is correct
3 Correct 259 ms 108676 KB Output is correct
4 Correct 261 ms 110248 KB Output is correct
5 Correct 255 ms 108836 KB Output is correct
6 Correct 232 ms 105324 KB Output is correct
7 Correct 202 ms 102344 KB Output is correct
8 Correct 240 ms 105296 KB Output is correct
9 Correct 207 ms 102352 KB Output is correct
10 Correct 235 ms 104412 KB Output is correct
11 Correct 215 ms 103876 KB Output is correct
12 Correct 214 ms 104176 KB Output is correct
13 Correct 207 ms 103960 KB Output is correct
14 Correct 245 ms 107912 KB Output is correct
15 Correct 242 ms 107856 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97228 KB Output is correct
2 Correct 41 ms 97228 KB Output is correct
3 Incorrect 40 ms 97400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97260 KB Output is correct
2 Correct 262 ms 109564 KB Output is correct
3 Correct 259 ms 108676 KB Output is correct
4 Correct 261 ms 110248 KB Output is correct
5 Correct 255 ms 108836 KB Output is correct
6 Correct 232 ms 105324 KB Output is correct
7 Correct 202 ms 102344 KB Output is correct
8 Correct 240 ms 105296 KB Output is correct
9 Correct 207 ms 102352 KB Output is correct
10 Correct 235 ms 104412 KB Output is correct
11 Correct 215 ms 103876 KB Output is correct
12 Correct 214 ms 104176 KB Output is correct
13 Correct 207 ms 103960 KB Output is correct
14 Correct 245 ms 107912 KB Output is correct
15 Correct 242 ms 107856 KB Output is correct
16 Incorrect 40 ms 97348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 97260 KB Output is correct
2 Correct 262 ms 109564 KB Output is correct
3 Correct 259 ms 108676 KB Output is correct
4 Correct 261 ms 110248 KB Output is correct
5 Correct 255 ms 108836 KB Output is correct
6 Correct 232 ms 105324 KB Output is correct
7 Correct 202 ms 102344 KB Output is correct
8 Correct 240 ms 105296 KB Output is correct
9 Correct 207 ms 102352 KB Output is correct
10 Correct 235 ms 104412 KB Output is correct
11 Correct 215 ms 103876 KB Output is correct
12 Correct 214 ms 104176 KB Output is correct
13 Correct 207 ms 103960 KB Output is correct
14 Correct 245 ms 107912 KB Output is correct
15 Correct 242 ms 107856 KB Output is correct
16 Incorrect 43 ms 97260 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 97228 KB Output is correct
2 Correct 41 ms 97228 KB Output is correct
3 Incorrect 40 ms 97400 KB Output isn't correct
4 Halted 0 ms 0 KB -