oj.uz

Submission #864193

# Submission time Handle Problem Language Result Execution time Memory
864193 2023-10-22T08:26:58 Z vjudge1 Financial Report (JOI21_financial) C++17
0 / 100
 168 ms 68404 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);
    }

    pair<ll, ll> dif(int k, int l, int r, ll v) {
        if (l == r) return {(sgt[k * 2 + 1] >= v && sgt[k * 2 + 1] != LLONG_MAX) * l, sgt[k * 2 + 1]};
        int m = (l + r) / 2;
        if (sgt[k * 2 + 1] >= v && sgt[k * 2 + 1] != LLONG_MAX) return dif(k * 2 + 1, m + 1, r, v);
        return dif(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);
        }
        ll ans1 = sgt.get(1, 0, n, a[i]) + 1;
        pair<ll, ll> ans2 = sgt.dif(1, 0, n, a[i]);
        dp[i] = max(ans1, ans2.first);
        if (ans2.first > ans1) a[i] = ans2.second;
        if (ans2.first == ans1) a[i] = min(a[i], ans2.second); 
        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:75:36: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |         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 3 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Incorrect 3 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 3 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Incorrect 3 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 3 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Incorrect 3 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 59 ms 30292 KB Output is correct
2 Incorrect 98 ms 30400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 44884 KB Output is correct
2 Correct 123 ms 44452 KB Output is correct
3 Correct 163 ms 44268 KB Output is correct
4 Correct 168 ms 44372 KB Output is correct
5 Runtime error 80 ms 68404 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

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