Submission #1069604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069604		caterpillow	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	28 / 100	4049 ms	19140 KiB

mizuyokan2

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'

/*

constraints suggest a sqrt solution
note that we can account for the high-low case by simply starting at a 0 before the query start

it is never optimal to make a "low" point involve multiple segments
we can consider low points as points, and edges as ranges such that the sum is greater than the node on either side
valid edges make a dag, and we can do a simple dp to solve subtasks 1 and 2

observations:

    say we are trying to find valid v for some current node u
    find the closest range such that the sum is greater than u
    then, there will be at most log A_max nodes after this who are invalid transitions
    this is because each time we reach an invalid node, our total range sum at least doubles

    also, we can rephrase validity as pfx[v - 1] - pfx[u] > a[v], or pfx[v - 1] - a[v] > pfx[u]

using the first observation, we can calculate dp[u] in reverse, with each state taking log n * log A_max time

 */

const ll inf = 1e18;
struct Seg1 {
    int n;
    vt<ll> seg;
    void init(int _n) {
        for (n = 1; n < _n; n *= 2);
        seg.resize(2 * n, inf);
    }
    ll query(int l, int r) {
        ll res = inf;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) res = min(res, seg[l++]);
            if (r & 1) res = min(seg[--r], res);
        }
        return res;
    }
    void upd(int i, ll v) {
        seg[i += n] = v;
        while (i /= 2) seg[i] = min(seg[2 * i], seg[2 * i + 1]);
    }
    int walk(ll x, int i) {
        if (i >= n) return i - n;
        if (seg[2 * i + 1] <= x) return walk(x, 2 * i + 1);
        else return walk(x, 2 * i);
    }

    vt<int> lhs, rhs;
    // find the last element in [l, r] such that a[i] <= x
    int walk_range(ll x, int l, int r) {
        lhs.clear();
        rhs.clear();
        int ol = l;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) lhs.pb(l++);
            if (r & 1) rhs.pb(--r);
        }
        for (int i : rhs) if (seg[i] <= x) return walk(x, i);
        reverse(all(lhs));
        for (int i : lhs) if (seg[i] <= x) return walk(x, i);
        return ol - 1;
    }
};

struct Seg2 {
    int n;
    vt<ll> seg;
    void init(int _n) {
        for (n = 1; n < _n; n *= 2);
        seg.resize(2 * n, -inf);
    }
    ll query(int l, int r) {
        ll res = -inf;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) res = max(res, seg[l++]);
            if (r & 1) res = max(seg[--r], res);
        }
        return res;
    }
    void upd(int i, ll v) {
        seg[i += n] = v;
        while (i /= 2) seg[i] = max(seg[2 * i], seg[2 * i + 1]);
    }
};

int solve(vt<ll> a) {
    int n = size(a);
    vt<ll> pfx(n + 1); // 1 - indexed
    F0R (i, n) pfx[i + 1] = pfx[i] + a[i];
    Seg1 seg;
    Seg2 dp;
    seg.init(n), dp.init(n);
    F0R (i, n) seg.upd(i, pfx[i] - a[i]);

    ROF (i, 0, n) {
        // find minimum j such that the sum from i + 1 to j is > a[i]
        ll cur = (i == n - 1); // special case for last guy

        int j = upper_bound(all(pfx), a[i] + pfx[i + 1]) - pfx.begin();
        j--;
        if (j == n) {
            dp.upd(i, cur);
            continue;
        }
        cur = 2; // we can at least end with a high

        int last = n;
        while (true) {
            int nxt = seg.walk_range(pfx[i + 1], j + 1, last - 1);

            cur = max(cur, dp.query(nxt + 1, last - 1) + 2);

            if (nxt == j) break;
            last = nxt;
        }

        dp.upd(i, cur);
    }

    ll ans = max(1ll, dp.query(0, 0));

    // special case for starting on a big guy
    int last = n;
    while (true) {
        int nxt = seg.walk_range(0, 0, last - 1);
        ans = max(ans, 1 + dp.query(nxt + 1, last - 1));

        if (nxt == -1) break;
        last = nxt;
    }

    return ans;
}

main() {
    cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;
    vt<ll> a(n); F0R (i, n) cin >> a[i];
    int q; cin >> q;
    F0R (i, q) {
        ll j, v; cin >> j >> v; j--;
        a[j] = v;
        int l, r; cin >> l >> r;
        vt<ll> tmp;
        FOR (j, l, r) {
            tmp.pb(a[j]);
        }
        cout << solve(tmp) << endl;
    }
}

Compilation message (stderr)

mizuyokan2.cpp:152:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  152 | main() {
      | ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11