Submission #1239131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239131		faruk	Financial Report (JOI21_financial)	C++20	100 / 100	434 ms	39176 KiB

Main

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

struct seggy {
    vector<int> t;
    int n;

    seggy() {}
    seggy(int n) : n(n) {
        t = vector<int>(2 * n);
    }

    int query(int l, int r) {
        int maxi = 0;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1)
                maxi = max(maxi, t[l++]);
            if (r & 1)
                maxi = max(maxi, t[--r]);
        }
        return maxi;
    }

    void mod(int idx, int val) {
        for (idx += n, t[idx] = val, idx /= 2; idx > 0; idx /= 2) 
            t[idx] = max(t[idx * 2], t[idx * 2 + 1]);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    cin >> n >> d;

    vector<pii> arr2(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr2[i].first;
        arr2[i].second = -i;
    }
    
    sort(all(arr2));
    map<pii, int> trans; int cnt = 0;
    vector<int> arr(n);
    for (auto x : arr2)
        arr[-x.second] = cnt++;
    
    set<int> big_hole;

    set<int> ids;
    vector<int> in_front_of_me(n, 1e9), cantuse(n, n);
    for (auto [val, id] : arr2) {
        id = -id;
        auto my_pnt = ids.insert(id).first;

        // change prev if exists
        if (my_pnt != ids.begin()) {
            auto prv = prev(my_pnt);
            if (id - *prv <= d and in_front_of_me[*prv] - *prv > d) 
                big_hole.erase(*prv);
            in_front_of_me[*prv] = id;
        }

        // adjust me
        if (next(my_pnt) != ids.end())
            in_front_of_me[id] = *next(my_pnt);
        if (in_front_of_me[id] - id > d)
            big_hole.insert(id);
        
        // calculate my cantuse
        if (big_hole.lower_bound(id) != big_hole.end())
            cantuse[id] = min(n, *big_hole.lower_bound(id) + d + 1);
    }

    seggy seg(n);
    int maxi = 1;
    vector<vector<int> > turn_off(n + 1);
    for (int i = 0; i < n; i++) {
        for (int j : turn_off[i])
            seg.mod(arr[j], 0);
        int my_val = seg.query(0, arr[i]) + 1;
        maxi = max(maxi, my_val);
        seg.mod(arr[i], my_val);
        turn_off[cantuse[i]].push_back(i);
    }

    cout << maxi << "\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