oj.uz

Submission #940183

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

#define int 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) ? 1ll : -1ll));

        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 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10704 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 1 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10704 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Incorrect 2 ms 10600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10704 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 1 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10704 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Incorrect 2 ms 10600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10704 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 1 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10704 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Incorrect 2 ms 10600 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 16724 KB Output is correct
2 Correct 127 ms 16720 KB Output is correct
3 Correct 127 ms 16696 KB Output is correct
4 Correct 128 ms 16696 KB Output is correct
5 Correct 127 ms 16720 KB Output is correct
6 Correct 137 ms 16712 KB Output is correct
7 Correct 127 ms 19164 KB Output is correct
8 Correct 121 ms 16692 KB Output is correct
9 Correct 127 ms 18412 KB Output is correct
10 Correct 127 ms 16696 KB Output is correct
11 Correct 135 ms 16868 KB Output is correct
12 Correct 147 ms 16720 KB Output is correct
13 Correct 127 ms 16732 KB Output is correct
14 Correct 139 ms 16692 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 16952 KB Output is correct
2 Incorrect 186 ms 16696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10704 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 1 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Correct 1 ms 10704 KB Output is correct
14 Correct 1 ms 10588 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Incorrect 2 ms 10600 KB Output isn't correct
17 Halted 0 ms 0 KB -