oj.uz

Submission #737952

# Submission time Handle Problem Language Result Execution time Memory
737952 2023-05-08T02:59:52 Z resting Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 91204 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) {
    if (ac4[i] > v) {
        ac4[i] = v; ac3.upd(i, v);
        //redo(i);
        if (i < n + 1)redo(i + 1);
        if (i)redo(i - 1);
    } else {
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 81664 KB Output is correct
2 Correct 50 ms 81644 KB Output is correct
3 Correct 40 ms 81712 KB Output is correct
4 Correct 42 ms 81688 KB Output is correct
5 Incorrect 48 ms 81716 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 81612 KB Output is correct
2 Correct 223 ms 91184 KB Output is correct
3 Correct 224 ms 90188 KB Output is correct
4 Correct 225 ms 91204 KB Output is correct
5 Correct 211 ms 90300 KB Output is correct
6 Correct 192 ms 87160 KB Output is correct
7 Correct 173 ms 85516 KB Output is correct
8 Correct 201 ms 87244 KB Output is correct
9 Correct 171 ms 85516 KB Output is correct
10 Correct 204 ms 86860 KB Output is correct
11 Correct 183 ms 86644 KB Output is correct
12 Correct 172 ms 86744 KB Output is correct
13 Correct 177 ms 86828 KB Output is correct
14 Correct 204 ms 89492 KB Output is correct
15 Correct 193 ms 89292 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 81664 KB Output is correct
2 Correct 50 ms 81644 KB Output is correct
3 Correct 40 ms 81712 KB Output is correct
4 Correct 42 ms 81688 KB Output is correct
5 Incorrect 48 ms 81716 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 81612 KB Output is correct
2 Correct 223 ms 91184 KB Output is correct
3 Correct 224 ms 90188 KB Output is correct
4 Correct 225 ms 91204 KB Output is correct
5 Correct 211 ms 90300 KB Output is correct
6 Correct 192 ms 87160 KB Output is correct
7 Correct 173 ms 85516 KB Output is correct
8 Correct 201 ms 87244 KB Output is correct
9 Correct 171 ms 85516 KB Output is correct
10 Correct 204 ms 86860 KB Output is correct
11 Correct 183 ms 86644 KB Output is correct
12 Correct 172 ms 86744 KB Output is correct
13 Correct 177 ms 86828 KB Output is correct
14 Correct 204 ms 89492 KB Output is correct
15 Correct 193 ms 89292 KB Output is correct
16 Correct 39 ms 81612 KB Output is correct
17 Execution timed out 4045 ms 90296 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 81612 KB Output is correct
2 Correct 223 ms 91184 KB Output is correct
3 Correct 224 ms 90188 KB Output is correct
4 Correct 225 ms 91204 KB Output is correct
5 Correct 211 ms 90300 KB Output is correct
6 Correct 192 ms 87160 KB Output is correct
7 Correct 173 ms 85516 KB Output is correct
8 Correct 201 ms 87244 KB Output is correct
9 Correct 171 ms 85516 KB Output is correct
10 Correct 204 ms 86860 KB Output is correct
11 Correct 183 ms 86644 KB Output is correct
12 Correct 172 ms 86744 KB Output is correct
13 Correct 177 ms 86828 KB Output is correct
14 Correct 204 ms 89492 KB Output is correct
15 Correct 193 ms 89292 KB Output is correct
16 Correct 50 ms 81612 KB Output is correct
17 Incorrect 1367 ms 91144 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 81664 KB Output is correct
2 Correct 50 ms 81644 KB Output is correct
3 Correct 40 ms 81712 KB Output is correct
4 Correct 42 ms 81688 KB Output is correct
5 Incorrect 48 ms 81716 KB Output isn't correct
6 Halted 0 ms 0 KB -