oj.uz

Submission #886403

# Submission time Handle Problem Language Result Execution time Memory
886403 2023-12-12T03:45:50 Z dong_liu Fish 2 (JOI22_fish2) C++17
0 / 100
 1 ms 2396 KB 
#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 >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -