oj.uz

Submission #940180

# Submission time Handle Problem Language Result Execution time Memory
940180 2024-03-07T06:27:35 Z haxorman Financial Report (JOI21_financial) C++14
12 / 100
 182 ms 11784 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int INF = 1e9 + 7;

int n, d, arr[mxN], seg[4*mxN], nex[mxN], dp[mxN];

void update(int ind, int val) {
    seg[ind+=SZ] = val;
    while (ind /= 2) {
        seg[ind] = max(seg[2*ind], seg[2*ind+1]);
    }
}

int query(int lo, int hi, int ind = 1, int l = 0, int r = SZ - 1) {
    if (lo > r || l > hi) {
        return -INF;
    }

    if (lo <= l && r <= hi) {
        return seg[ind];
    }

    int mid = (l+r)/2;
    return max(query(lo,hi,2*ind,l,mid), query(lo,hi,2*ind+1,mid+1,r));
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> d;
    
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    arr[n] = INT_MAX;
    
    vector<int> st = {n};
    for (int i = n-1; i >= 0; --i) {
        while (st.size() && arr[st.back()] <= arr[i]) {
            st.pop_back();
        }
        nex[i] = st.back();
        st.push_back(i);

        if (i < n-1) {
            update(i, -INF);
        }
    }
    update(n-1, 1);
    update(n, -INF);

    for (int i = n-2; i >= 0; --i) {
        dp[i] = max(query(nex[i], min(n, nex[i]+d-1)) + 1,
                   (query(i, i+d) ? 1 : -1));

        update(i, (dp[i] < 0 ? -INF : dp[i]));
    }

    cout << query(0, n-1) << "\n";
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6620 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 6584 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6620 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 6584 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6620 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 6584 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 9560 KB Output is correct
2 Correct 132 ms 9236 KB Output is correct
3 Correct 131 ms 9560 KB Output is correct
4 Correct 131 ms 9576 KB Output is correct
5 Correct 131 ms 9564 KB Output is correct
6 Correct 130 ms 9568 KB Output is correct
7 Correct 137 ms 11784 KB Output is correct
8 Correct 123 ms 9560 KB Output is correct
9 Correct 131 ms 10704 KB Output is correct
10 Correct 136 ms 9556 KB Output is correct
11 Correct 131 ms 9568 KB Output is correct
12 Correct 135 ms 9556 KB Output is correct
13 Correct 130 ms 9748 KB Output is correct
14 Correct 126 ms 9556 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 9580 KB Output is correct
2 Incorrect 182 ms 9560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6620 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6604 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6608 KB Output is correct
13 Correct 1 ms 6584 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -