Submission #1219475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219475		Double_Slash	Fish 2 (JOI22_fish2)	C++20	100 / 100	1143 ms	39472 KiB

fish2

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Val = array<int, 3>;
 
const int INF = 1e9;
int n, q;
ll x[100002];
set<int> s[100001], e[100001];
 
pll operator+(const pll &a, const pll &b) { return {a.first + b.first, max(a.second, a.first + b.second)}; }
 
void operator+=(pll &p, ll v) { p.first += v, p.second += v; }
 
struct PreMin {
    int n = 1;
    vector<pll> st;
 
    PreMin(int _n) {
        while (n < _n) n <<= 1;
        st.resize(n << 1);
    }
 
    void update(int i, ll v, bool point = false) {
        if (point) update(i + 1, -v, false);
        for (st[i += n] += v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }
 
    ll query(int r) {
        ll ret = 0;
        for (r += n; r & (r - 1); r >>= 1) {
            if (r & 1) ret += st[--r].first;
        }
        return ret;
    }
 
    int walksuf(int l, ll x) {
        x -= query(l);
        for (l += n;; l >>= 1) {
            if (l & 1) {
                if (st[l].second > x) {
                    while (l < n) {
                        if (st[l <<= 1].second <= x) {
                            x -= st[l].first;
                            l ^= 1;
                        }
                    }
                    return l - n;
                } else x -= st[l++].first;
                if (not (l & (l - 1))) return n;
            }
        }
    }
};
 
Val operator+(const Val &a, const Val &b) {
    if (a[1] < a[0] + b[1]) return {a[0] + b[0], a[1], a[2]};
    else if (a[0] + b[1] < a[1]) return {a[0] + b[0], a[0] + b[1], b[2]};
    else return {a[0] + b[0], a[1], a[2] + b[2]};
}
 
void operator+=(Val &v, int x) { v[0] += x, v[1] += x; }
 
struct CntPreMin {
    int n;
    vector<Val> st;
 
    CntPreMin(int n) : n(n), st(n << 1, {0, 0, 1}) {}
 
    void update(int i, int v) {
        for (st[i += n] += v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }
 
    Val query(int l, int r) {
        Val lagg{0, INF}, ragg{INF, INF};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lagg = lagg + st[l++];
            if (r & 1) ragg = st[--r] + ragg;
        }
        return lagg + ragg;
    }
};
 
int main() {
    cin >> n;
    PreMin leat{n + 1}, reat{n + 2}, ranges{n + 2};
    leat.update(n - 1, x[0] = 1e18);
    reat.update(n, x[n + 1] = 1e18);
    auto ps = [&] (int i) { return i ? x[i + 1] - reat.query(i + 1) : 0ll; };
    CntPreMin st{n + 2};
    for (int i = 1; i <= n; ++i) e[i].emplace(0);
    auto rem = [&] (int l, int r) {
        if (r == *e[l].rbegin()) ranges.update(l, *next(e[l].rbegin()) - r, true);
        e[l].erase(r);
        s[r].erase(l);
        st.update(l, -1);
        st.update(r + 1, 1);
    };
    auto add = [&] (int i) {
        for (int l = i, r = i;;) {
            for (ll psl = ps(l - 1), psr = ps(r);;) {
                if (psr - psl >= x[r + 1]) psr = ps(r = reat.walksuf(r, -psl));
                else if (psr - psl >= x[l - 1]) psl = ps((l = n - leat.walksuf(n - l, psr)) - 1);
                else break;
            }
            if (l == 1 and r == n) break;
            if (not e[l].contains(r)) {
                if (r > *e[l].rbegin()) ranges.update(l, r - *e[l].rbegin(), true);
                e[l].emplace(r);
                s[r].emplace(l);
                st.update(l, 1);
                st.update(r + 1, -1);
            }
            if (x[l - 1] < x[r + 1]) --l;
            else ++r;
        }
    };
    auto upd = [&] (int a, int b = 0) {
        if (not b) cin >> b;
        reat.update(a, -(1 + (a >= 2)) * (b -= x[a]));
        if (a >= 2) reat.update(a - 1, b);
        if (a < n) {
            leat.update(0, b * (1 + (a == n - 1)));
            leat.update(n - a, -2 * b);
            if (a < n - 1) leat.update(n - (a + 1), b);
        }
        x[a] += b;
        if (b < 0) {
            if (a > 1) {
                ll P = ps(a - 1);
                for (auto it = s[a - 1].end(); it != s[a - 1].begin();) {
                    if (int l = *prev(it); P - ps(l - 1) >= min(x[a], x[l - 1])) rem(*prev(it), a - 1);
                    else --it;
                }
            }
            add(a);
            if (a < n) {
                ll P = ps(a);
                for (auto it = e[a + 1].end(); *prev(it);) {
                    if (int r = *prev(it); ps(r) - P >= min(x[a], x[r + 1])) rem(a + 1, *prev(it));
                    else --it;
                }
            }
        } else if (b > 0) {
            if (a > 1) add(a - 1);
            for (int l = 0; l < a;) {
                l = ranges.walksuf(l + 1, a - 1);
                if (l > a) break;
                ll P = ps(l - 1);
                for (auto it = e[l].end(); *prev(it);) {
                    if (int r = *prev(it); ps(r) - P >= min(x[l - 1], x[r + 1])) rem(l, r);
                    else --it;
                }
            }
            if (a < n) add(a + 1);
        }
    };
    for (int i = 1; i <= n; ++i) upd(i);
    cin >> q;
    while (q--) {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1) upd(a, b);
        else {
            int l = a;
            for (ll P = ps(a - 1);;) {
                int i = reat.walksuf(l, -P);
                if (i >= b) break;
                l = i + 1;
            }
            int r = b;
            for (ll P = ps(b);;) {
                int i = n - leat.walksuf(n - r, P);
                if (i <= a) break;
                r = i - 1;
            }
            cout << st.query(l, r + 1)[2] << endl;
        }
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17