oj.uz

Submission #737945

# Submission time Handle Problem Language Result Execution time Memory
737945 2023-05-08T02:52:27 Z resting Fish 2 (JOI22_fish2) C++17
8 / 100
 227 ms 90876 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){
        redo(i);
    }
    else {
        ac4[i] = v; ac3.upd(i, v);
        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);
        }
        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 Incorrect 36 ms 81716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81660 KB Output is correct
2 Correct 211 ms 90812 KB Output is correct
3 Correct 216 ms 89936 KB Output is correct
4 Correct 211 ms 90876 KB Output is correct
5 Correct 206 ms 89976 KB Output is correct
6 Correct 177 ms 86992 KB Output is correct
7 Correct 162 ms 85308 KB Output is correct
8 Correct 174 ms 86888 KB Output is correct
9 Correct 164 ms 85328 KB Output is correct
10 Correct 182 ms 86600 KB Output is correct
11 Correct 172 ms 86344 KB Output is correct
12 Correct 171 ms 86480 KB Output is correct
13 Correct 168 ms 86500 KB Output is correct
14 Correct 227 ms 89292 KB Output is correct
15 Correct 193 ms 89044 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 81716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81660 KB Output is correct
2 Correct 211 ms 90812 KB Output is correct
3 Correct 216 ms 89936 KB Output is correct
4 Correct 211 ms 90876 KB Output is correct
5 Correct 206 ms 89976 KB Output is correct
6 Correct 177 ms 86992 KB Output is correct
7 Correct 162 ms 85308 KB Output is correct
8 Correct 174 ms 86888 KB Output is correct
9 Correct 164 ms 85328 KB Output is correct
10 Correct 182 ms 86600 KB Output is correct
11 Correct 172 ms 86344 KB Output is correct
12 Correct 171 ms 86480 KB Output is correct
13 Correct 168 ms 86500 KB Output is correct
14 Correct 227 ms 89292 KB Output is correct
15 Correct 193 ms 89044 KB Output is correct
16 Incorrect 36 ms 81680 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81660 KB Output is correct
2 Correct 211 ms 90812 KB Output is correct
3 Correct 216 ms 89936 KB Output is correct
4 Correct 211 ms 90876 KB Output is correct
5 Correct 206 ms 89976 KB Output is correct
6 Correct 177 ms 86992 KB Output is correct
7 Correct 162 ms 85308 KB Output is correct
8 Correct 174 ms 86888 KB Output is correct
9 Correct 164 ms 85328 KB Output is correct
10 Correct 182 ms 86600 KB Output is correct
11 Correct 172 ms 86344 KB Output is correct
12 Correct 171 ms 86480 KB Output is correct
13 Correct 168 ms 86500 KB Output is correct
14 Correct 227 ms 89292 KB Output is correct
15 Correct 193 ms 89044 KB Output is correct
16 Incorrect 41 ms 81588 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 81716 KB Output isn't correct
2 Halted 0 ms 0 KB -