Submission #864305

#	Time	Username	Problem	Language	Result	Execution time	Memory
864305		vjudge1	Financial Report (JOI21_financial)	C++17	17 / 100	188 ms	42668 KiB

Main

#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});
        }
        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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:97: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]
   97 |         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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35