| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 737958 | resting | Fish 2 (JOI22_fish2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 clear(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);
}
}
void redo(int i, bool extendleft, bool extendright) {
//cout << "REDO " << i << endl;
//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);
if (wl < i - 1 && !extendleft) break;
if (wr > i + 1 && !extendright) break;
//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]) {
if (!extendright) break;
r++;
} else {
if (!extendleft) break;
l--;
}
}
void upd(int i, ll v) {
ac4[i] = v; ac3.upd(i, v);
clear(i);
if (i < n + 1)clear(i + 1);
if (i)clear(i - 1);
redo(i, 1, 1);
if (i < n + 1)redo(i + 1, 0, 1);
if (i)redo(i - 1, 1, 0);
}
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();
}