Submission #766004

#	Time	Username	Problem	Language	Result	Execution time	Memory
766004		pandapythoner	Financial Report (JOI21_financial)	C++14	100 / 100	179 ms	18744 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

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

    void build(int _n) {
        n = 1;
        while (n < _n) {
            n *= 2;
        }
        t.assign(n + n, 0);
    }

    void chng(int i, int x) {
        i += n;
        t[i] = x;
        for (i /= 2; i > 0; i /= 2) {
            t[i] = max(t[i + i], t[i + i + 1]);
        }
    }

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

int n, d;
vector<ll> a;
vector<int> go;
SGT sgt;

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> d;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        cin >> a[i];
    }
    go.resize(n);
    set<pair<int, int>> sgs;
    vector<pair<ll, int>> srtd(n);
    for (int i = 0; i < n; i += 1) {
        srtd[i] = make_pair(a[i], i);
    }
    sort(all(srtd), [](const pair<ll, int> &a, const pair<ll, int> &b) {
        if (a.first != b.first) {
            return a.first < b.first;
        }
        return a.second > b.second;
    });
    vector<int> dp(n, 0);
    sgt.build(n);
    int mx_dp = 0;
    for (auto [x, i] : srtd) {
        int r = i;
        int l = max(0, i - d);
        auto it = sgs.upper_bound(make_pair(l, l - 1));
        if (it != sgs.begin()) {
            auto pit = prev(it);
            if (pit->second >= l) {
                l = min(l, pit->first);
                r = max(r, pit->second);
                sgs.erase(pit);
            }
        }
        if (it != sgs.end() && it->first <= r) {
            r = max(r, it->second);
            l = min(l, it->first);
            sgs.erase(it);
        }
        sgs.insert(make_pair(l, r));
        int t = l;
        int mx = 0;
        mx = sgt.get(l, i);
        dp[i] = mx + 1;
        mx_dp = max(mx_dp, dp[i]);
        sgt.chng(i, dp[i]);
    }
    cout << mx_dp << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for (auto [x, i] : srtd) {
      |               ^
Main.cpp:99:13: warning: unused variable 't' [-Wunused-variable]
   99 |         int t = l;
      |             ^

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