oj.uz

Submission #864306

# Submission time Handle Problem Language Result Execution time Memory
864306 2023-10-22T11:09:33 Z vjudge1 Financial Report (JOI21_financial) C++17
17 / 100
 174 ms 42672 KB 
#include <bits/stdc++.h>

using namespace std;

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

vector<ll> a;

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));

struct FenwickTree {
    vector<ll> fwt;
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, d;
    cin >> n >> d;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    if (d == 1) {
        deque<ll> dq;
        int ans = 0;
        dq.push_back(a[n]);
        for (int i = n - 1; i > 0; i--) {
            while (dq.size() && a[i] >= dq.front()) dq.pop_front();
            dq.push_front(a[i]);
            ans = max(ans, (int) dq.size());
        }
        cout << ans;
        return 0;
    }
    if (d == n) {
        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 || mn != *lis[dp[i]].begin()) sgt.update(1, 0, n, dp[i], a[i]);
            ans = max(ans, dp[i]);
            // cout << i << " : " << dp[i] << endl;
        }
        cout << ans;
        return 0;
    }
    for (int i = 0; i < n; i++) a[i] = a[i + 1];
    for (ll mask = 1; mask < (1 << n); mask++) {
        bool flag = 1;
        vector<pair<ll, ll>> v;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) v.push_back({a[j], j});
        }
        if (v.back().second != n - 1) continue;
        ll mx = v[0].first, res = 1;
        for (int j = 1; j < v.size(); j++) {
            if (v[j].second - v[j - 1].second > d) flag = 0;
            if (v[j].first > mx) {
                mx = v[j].first;
                res++;
            }
        }
        if (!flag) continue;
        ans = max(ans, res);
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int j = 1; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
Main.cpp:82:40: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |             if (lis[dp[i]].size() == 1 || mn != *lis[dp[i]].begin()) sgt.update(1, 0, n, dp[i], a[i]);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12124 KB Output is correct
2 Correct 32 ms 12120 KB Output is correct
3 Correct 27 ms 12120 KB Output is correct
4 Correct 33 ms 12124 KB Output is correct
5 Correct 28 ms 12120 KB Output is correct
6 Correct 27 ms 12124 KB Output is correct
7 Correct 26 ms 14428 KB Output is correct
8 Correct 31 ms 12124 KB Output is correct
9 Correct 27 ms 13748 KB Output is correct
10 Correct 28 ms 12124 KB Output is correct
11 Correct 27 ms 12136 KB Output is correct
12 Correct 28 ms 12124 KB Output is correct
13 Correct 25 ms 12212 KB Output is correct
14 Correct 26 ms 12124 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 42580 KB Output is correct
2 Correct 124 ms 42464 KB Output is correct
3 Correct 174 ms 42528 KB Output is correct
4 Correct 162 ms 42664 KB Output is correct
5 Correct 146 ms 42664 KB Output is correct
6 Correct 156 ms 42644 KB Output is correct
7 Correct 93 ms 42584 KB Output is correct
8 Correct 116 ms 42672 KB Output is correct
9 Correct 98 ms 42528 KB Output is correct
10 Correct 118 ms 42580 KB Output is correct
11 Correct 162 ms 42576 KB Output is correct
12 Correct 97 ms 42596 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -