Submission #763698

#	Time	Username	Problem	Language	Result	Execution time	Memory
763698		adaawf	Financial Report (JOI21_financial)	C++14	100 / 100	520 ms	132972 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int n, d, a[2000005], t[2000005];
multiset<int> q[2000005];
void update(int v, int tl, int tr, int x, int y, int w) {
    if (tr < x || x < tl) {
        return;
    }
    if (tl == tr) {
        if (w == 0) q[v].erase(q[v].find(y));
        if (w == 1) q[v].insert(y);
        if (q[v].empty()) t[v] = 0;
        else t[v] = (*q[v].rbegin());
        return;
    }
    int mid = (tl + tr) / 2;
    update(v * 2, tl, mid, x, y, w);
    update(v * 2 + 1, mid + 1, tr, x, y, w);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
    if (r < 0) return 0;
    if (tr < l || r < tl) return 0;
    if (l <= tl && tr <= r) {
        return t[v];
    }
    int mid = (tl + tr) / 2;
    return max(sum(v * 2, tl, mid, l, r), sum(v * 2 + 1, mid + 1, tr, l, r));
}
int f[2000005];
vector<int> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v.push_back(a[i]);
    }
    set<pair<int, int>> s;
    sort(v.begin(), v.end());
    v.resize(distance(v.begin(), unique(v.begin(), v.end())));
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        while (i + (*s.begin()).second > d) {
            update(1, 1, v.size(), (*s.begin()).first, f[-(*s.begin()).second], 0);
            s.erase(s.begin());
        }
        f[i] = sum(1, 1, v.size(), 1, a[i] - 1) + 1;
        update(1, 1, v.size(), a[i], f[i], 1);
        res = max(res, f[i]);
        s.insert({a[i], -i});
    }
    cout << res;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35