oj.uz

Submission #864174

# Submission time Handle Problem Language Result Execution time Memory
864174 2023-10-22T08:00:14 Z vjudge1 Financial Report (JOI21_financial) C++17
5 / 100
 151 ms 42660 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);
        for (int i = 0; i < n; i++) sgt[i] = 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, dp[i - d - 1], *lis[dp[i - d - 1]].begin());
            }
            else sgt.update(1, 0, n, dp[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:64:36: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |         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 9820 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 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 2 ms 9816 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 3 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Incorrect 2 ms 9820 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 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 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 2 ms 9816 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 3 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Incorrect 2 ms 9820 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 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 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 2 ms 9816 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 3 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Incorrect 2 ms 9820 KB Output isn't correct
16 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 Incorrect 88 ms 28492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 42656 KB Output is correct
2 Correct 112 ms 42544 KB Output is correct
3 Correct 151 ms 42580 KB Output is correct
4 Correct 149 ms 42576 KB Output is correct
5 Correct 132 ms 42660 KB Output is correct
6 Correct 147 ms 42604 KB Output is correct
7 Correct 96 ms 42580 KB Output is correct
8 Correct 127 ms 42580 KB Output is correct
9 Correct 88 ms 42464 KB Output is correct
10 Correct 115 ms 42392 KB Output is correct
11 Correct 146 ms 42580 KB Output is correct
12 Correct 108 ms 42532 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 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 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 2 ms 9816 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 3 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Incorrect 2 ms 9820 KB Output isn't correct
16 Halted 0 ms 0 KB -