Submission #521721

#	Time	Username	Problem	Language	Result	Execution time	Memory
521721		surgutti	Financial Report (JOI21_financial)	C++17	100 / 100	414 ms	20844 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int n, d; cin >> n >> d;
    vector<int> a(n);

    for (int &x : a)    cin >> x;

    vector<int> v = a;
    v.push_back(-1);

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int &x : a)    x = lower_bound(v.begin(), v.end(), x) - v.begin();

    int tree_size = 1;

    while (tree_size < (int) v.size())  tree_size <<= 1;

    vector<int> tree(tree_size << 1);

    auto query = [&tree, tree_size] (int l, int r) {
        int res = 0;
        for (l += tree_size, r += tree_size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1)  res = max(res, tree[l++]);
            if (r & 1)  res = max(res, tree[--r]);
        }
        return res;
    };

    int ans = 0;
    auto update = [&tree, tree_size, &ans] (int p, int v) {
        ans = max(ans, v);
        for (tree[p += tree_size] = v; p >>= 1; )
            tree[p] = max(tree[p << 1 | 0], tree[p << 1 | 1]);
    };

    set<pair<int, int>> between, past;

    for (int i = 0; i < n; i++) {
        update(a[i], max(query(0, a[i] - 1) + 1, query(a[i], a[i])));
        
        between.insert({a[i], i});
        if (i >= d) {
            between.erase({a[i - d], i - d});
            past.insert({a[i - d], i - d});
            
            while (past.size() && between.begin()->first > past.begin()->first) {
                update(past.begin()->first, 0);
                past.erase(past.begin());
            }
        }
    }
    
    cout << ans << '\n';
}

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