Submission #886404

#	Time	Username	Problem	Language	Result	Execution time	Memory
886404		dong_liu	Fish 2 (JOI22_fish2)	C++17	25 / 100	4070 ms	4024 KiB

fish2

#include <bits/stdc++.h>
using namespace std;

#define ar aay
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int N = 1e5+5;
const i64 INF = 1e18;

int n, q;
i64 a[N], sm[N], c[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i, x;
            cin >> i >> x;
            a[i] = x;
        } else {
            int s, e;
            cin >> s >> e;
            for (int i = 1; i <= n; i++) sm[i] = sm[i - 1] + a[i], c[i] = 0;
            vector<pair<int, i64>> v;
            v.push_back({s - 1, INF});
            for (int i = s; i <= e + 1; i++) {
                while (!v.empty() && v.back().second <= (i == e + 1 ? INF : a[i])) {
                    int l = v.back().first, r = i;
                    if (l == s - 1 && r == e + 1) break;
                    v.pop_back();
                    if (sm[r - 1] - sm[l] < min(l == s - 1 ? INF : a[l], r == e + 1 ? INF : a[r])) c[l + 1]++, c[r]--;
                }
                int l = v.back().first, r = i;
                if (!(l == s - 1 && r == e + 1) && sm[r - 1] - sm[l] < min(l == s - 1 ? INF : a[l], r == e + 1 ? INF : a[r]))
                    c[l + 1]++, c[r]--;
                v.push_back(make_pair(i, a[i]));
            }
            for (int i = 1; i <= n; i++) c[i] += c[i - 1];
            int k = 0;
            for (int i = s; i <= e; i++) if (!c[i]) k++;
            cout << k << '\n';
        }
    }
}

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