oj.uz

Submission #710384

# Submission time Handle Problem Language Result Execution time Memory
710384 2023-03-15T07:59:48 Z PixelCat Fish 2 (JOI22_fish2) C++14
8 / 100
 31 ms 6600 KB 
#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.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 29 ms 6216 KB Output is correct
3 Correct 27 ms 5964 KB Output is correct
4 Correct 27 ms 6288 KB Output is correct
5 Correct 27 ms 5964 KB Output is correct
6 Correct 28 ms 6600 KB Output is correct
7 Correct 25 ms 5840 KB Output is correct
8 Correct 31 ms 6564 KB Output is correct
9 Correct 26 ms 5784 KB Output is correct
10 Correct 26 ms 6196 KB Output is correct
11 Correct 25 ms 5840 KB Output is correct
12 Correct 27 ms 5832 KB Output is correct
13 Correct 26 ms 5852 KB Output is correct
14 Correct 26 ms 6216 KB Output is correct
15 Correct 26 ms 6160 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 29 ms 6216 KB Output is correct
3 Correct 27 ms 5964 KB Output is correct
4 Correct 27 ms 6288 KB Output is correct
5 Correct 27 ms 5964 KB Output is correct
6 Correct 28 ms 6600 KB Output is correct
7 Correct 25 ms 5840 KB Output is correct
8 Correct 31 ms 6564 KB Output is correct
9 Correct 26 ms 5784 KB Output is correct
10 Correct 26 ms 6196 KB Output is correct
11 Correct 25 ms 5840 KB Output is correct
12 Correct 27 ms 5832 KB Output is correct
13 Correct 26 ms 5852 KB Output is correct
14 Correct 26 ms 6216 KB Output is correct
15 Correct 26 ms 6160 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 29 ms 6216 KB Output is correct
3 Correct 27 ms 5964 KB Output is correct
4 Correct 27 ms 6288 KB Output is correct
5 Correct 27 ms 5964 KB Output is correct
6 Correct 28 ms 6600 KB Output is correct
7 Correct 25 ms 5840 KB Output is correct
8 Correct 31 ms 6564 KB Output is correct
9 Correct 26 ms 5784 KB Output is correct
10 Correct 26 ms 6196 KB Output is correct
11 Correct 25 ms 5840 KB Output is correct
12 Correct 27 ms 5832 KB Output is correct
13 Correct 26 ms 5852 KB Output is correct
14 Correct 26 ms 6216 KB Output is correct
15 Correct 26 ms 6160 KB Output is correct
16 Incorrect 0 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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