Submission #710384

#	Time	Username	Problem	Language	Result	Execution time	Memory
710384		PixelCat	Fish 2 (JOI22_fish2)	C++14	8 / 100	31 ms	6600 KiB

fish2

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;
const int INF = 1e18;

int a[MAXN];
int su[MAXN];
int le[MAXN];
int ri[MAXN];

int sum(int l, int r) {
    int res = su[r];
    if(l > 0) res -= su[l - 1];
    return res;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n; cin >> n;
    For(i, 1, n) cin >> a[i];
    a[0] = a[n + 1] = INF;
    su[0] = a[0];
    For(i, 1, n + 1) su[i] = su[i - 1] + a[i];
    int q; cin >> q;
    For(r, 1, n) {
        int hi = r;
        int lo = 0;
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            if(sum(mi, r - 1) >= a[r]) lo = mi;
            else hi = mi;
        }
        le[r] = lo;

        hi = n + 1;
        lo = r;
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            if(sum(r + 1, mi) >= a[r]) hi = mi;
            else lo = mi;
        }
        ri[r] = hi;
    }
    // For(i, 1, n) cout << le[i] << " \n"[i == n];
    // For(i, 1, n) cout << ri[i] << " \n"[i == n];
    vector<pii> v;
    For(i, 1, n) {
        v.eb(le[i] + 1, i);
    }
    sort(all(v));
    reverse(all(v));
    priority_queue<int, vector<int>, greater<int>> pq;
    int mx1 = 1;
    int mn = n;
    int ans = 0;
    For(i, 1, n) {
        if(i > 1) mn = max(mn, ri[i - 1]);
        if(mn >= n + 1) break;
        while(sz(v) && v.back().F <= i) {
            pq.emplace(v.back().S);
            v.pop_back();
        }
        while(sz(pq) && pq.top() <= mn) {
            mx1 = max(mx1, pq.top());
            pq.pop();
        }
        mn = min(mn, mx1);
        if(mn <= i) ans++;
        // cout << i << " " << mn << " " << mx1 << "\n";
    }
    cout << ans << "\n";
    return 0;
}

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