oj.uz

Submission #951654

# Submission time Handle Problem Language Result Execution time Memory
951654 2024-03-22T08:56:23 Z qwe1rt1yuiop1 Fish 2 (JOI22_fish2) C++14
8 / 100
 17 ms 6468 KB 
#include <bits/stdc++.h>
#define int long long
// using ll = long long;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
using pii = pair<int, int>;

vector<int> ll, rr, v, p, ok;

void dfs(int x, int l, int r)
{
    ok[x] = 1;
    if (ll[x] != -1 && v[x] <= p[x - 1] - p[l - 1])
        dfs(ll[x], l, x - 1);
    if (rr[x] != -1 && v[x] <= p[r] - p[x])
        dfs(rr[x], x + 1, r);
}

void solve()
{
    int n;
    cin >> n;
    v.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    p = v;
    for (int i = 1; i <= n; ++i)
        p[i] += p[i - 1];
    v[0] = INT_MAX, v.emplace_back(INT_MAX);
    --v[0];

    vector<int> l(n + 2, -1), r(n + 2, -1);

    vector<int> stk;
    stk.emplace_back(0);
    for (int i = 1; i <= n; ++i)
    {
        while (v[stk.back()] < v[i])
            stk.pop_back();
        l[i] = stk.back();
        stk.emplace_back(i);
    }
    stk.clear();
    stk.emplace_back(n + 1);
    for (int i = n; i >= 1; --i)
    {
        while (v[stk.back()] <= v[i])
            stk.pop_back();
        r[i] = stk.back();
        stk.emplace_back(i);
    }

    ll.assign(n + 2, -1), rr = ll;

    for (int i = 1; i <= n; ++i)
    {
        if (v[l[i]] < v[r[i]])
        {
            assert(rr[l[i]] == -1);
            rr[l[i]] = i;
        }
        else
        {
            assert(ll[r[i]] == -1);
            ll[r[i]] = i;
        }
    }

    ok.assign(n + 1, 0);
    dfs(rr[0], 1, n);
    cout << accumulate(all(ok), 0) << '\n';
}

/*
 */

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 348 KB Output is correct
2 Correct 10 ms 5852 KB Output is correct
3 Correct 9 ms 5852 KB Output is correct
4 Correct 10 ms 5708 KB Output is correct
5 Correct 9 ms 5708 KB Output is correct
6 Correct 14 ms 5708 KB Output is correct
7 Correct 9 ms 5964 KB Output is correct
8 Correct 17 ms 6468 KB Output is correct
9 Correct 13 ms 6080 KB Output is correct
10 Correct 12 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 11 ms 6004 KB Output is correct
13 Correct 11 ms 6216 KB Output is correct
14 Correct 11 ms 6464 KB Output is correct
15 Correct 12 ms 6432 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 348 KB Output is correct
2 Correct 10 ms 5852 KB Output is correct
3 Correct 9 ms 5852 KB Output is correct
4 Correct 10 ms 5708 KB Output is correct
5 Correct 9 ms 5708 KB Output is correct
6 Correct 14 ms 5708 KB Output is correct
7 Correct 9 ms 5964 KB Output is correct
8 Correct 17 ms 6468 KB Output is correct
9 Correct 13 ms 6080 KB Output is correct
10 Correct 12 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 11 ms 6004 KB Output is correct
13 Correct 11 ms 6216 KB Output is correct
14 Correct 11 ms 6464 KB Output is correct
15 Correct 12 ms 6432 KB Output is correct
16 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 10 ms 5852 KB Output is correct
3 Correct 9 ms 5852 KB Output is correct
4 Correct 10 ms 5708 KB Output is correct
5 Correct 9 ms 5708 KB Output is correct
6 Correct 14 ms 5708 KB Output is correct
7 Correct 9 ms 5964 KB Output is correct
8 Correct 17 ms 6468 KB Output is correct
9 Correct 13 ms 6080 KB Output is correct
10 Correct 12 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 11 ms 6004 KB Output is correct
13 Correct 11 ms 6216 KB Output is correct
14 Correct 11 ms 6464 KB Output is correct
15 Correct 12 ms 6432 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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