oj.uz

Submission #864163

# Submission time Handle Problem Language Result Execution time Memory
864163 2023-10-22T07:50:23 Z vjudge1 Financial Report (JOI21_financial) C++17
5 / 100
 154 ms 42796 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

ll a[(int) 3e5 + 10];

struct SegmentTree {
    vector<ll> sgt;

    SegmentTree(int n) {
        sgt.resize(n, LLONG_MAX);
    }

    ll get(int k, int l, int r, ll v) {
        if (l == r) return l;
        int m = (l + r) / 2;
        if (sgt[k * 2 + 1] < v) return get(k * 2 + 1, m + 1, r, v);
        return get(k * 2, l, m, v);
    }

    void update(int k, int l, int r, int i, ll v) {
        if (l > i || r < i) return;
        if (l == r) {
            sgt[k] = v;
            return;
        }
        int m = (l + r) / 2;
        update(k * 2, l, m, i, v);
        update(k * 2 + 1, m + 1, r, i, v);
        sgt[k] = min(sgt[k * 2], sgt[k * 2 + 1]);
    }
} sgt(4 * (3e5 + 10));

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, d;
    cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    multiset<ll> lis[n + 10];
    lis[0].insert(0);
    sgt.update(1, 0, n, 0, 0);
    ll dp[n + 10];
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        ll mn;
        if (i > d + 1) {
            mn = *lis[dp[i - d - 1]].begin();
            lis[dp[i - d - 1]].erase(lis[dp[i - d - 1]].find(a[i - d - 1]));
            if (lis[dp[i - d - 1]].size()) {
                if (*lis[dp[i - d - 1]].begin() != mn) sgt.update(1, 0, n, i - d - 1, *lis[dp[i - d - 1]].begin());
            }
            else sgt.update(1, 0, n, i - d - 1, LLONG_MAX);
        }
        dp[i] = sgt.get(1, 0, n, a[i]) + 1;
        if (lis[dp[i]].size()) mn = *lis[dp[i]].begin();
        lis[dp[i]].insert(a[i]);
        if (lis[dp[i]].size() == 1 || a[i] < mn) sgt.update(1, 0, n, dp[i], a[i]);
        ans = max(ans, dp[i]);
        // cout << i << " : " << dp[i] << endl;
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:63:36: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |         if (lis[dp[i]].size() == 1 || a[i] < mn) sgt.update(1, 0, n, dp[i], a[i]);
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9612 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9748 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Correct 2 ms 10072 KB Output is correct
21 Incorrect 2 ms 9820 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9612 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9748 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Correct 2 ms 10072 KB Output is correct
21 Incorrect 2 ms 9820 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9612 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9748 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Correct 2 ms 10072 KB Output is correct
21 Incorrect 2 ms 9820 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 28500 KB Output is correct
2 Correct 96 ms 28508 KB Output is correct
3 Incorrect 113 ms 28500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 42576 KB Output is correct
2 Correct 108 ms 42548 KB Output is correct
3 Correct 146 ms 42576 KB Output is correct
4 Correct 154 ms 42796 KB Output is correct
5 Correct 127 ms 42664 KB Output is correct
6 Correct 132 ms 42576 KB Output is correct
7 Correct 88 ms 42580 KB Output is correct
8 Correct 129 ms 42552 KB Output is correct
9 Correct 89 ms 42340 KB Output is correct
10 Correct 114 ms 42496 KB Output is correct
11 Correct 143 ms 42672 KB Output is correct
12 Correct 96 ms 42712 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9612 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9748 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9816 KB Output is correct
20 Correct 2 ms 10072 KB Output is correct
21 Incorrect 2 ms 9820 KB Output isn't correct
22 Halted 0 ms 0 KB -