Submission #1091212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091212		ljtunas	Financial Report (JOI21_financial)	C++17	100 / 100	322 ms	27252 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 100;

int a[N], f[N], IT[N << 2], perm[N], kount[N], rightMost[N], leftMost[N];

void Update(int k, int l, int r, int u, int v) {
    if (l == r) { IT[k] = v; return; }
    int m = l + r >> 1;
    if (u <= m) Update(k << 1, l, m, u, v);
    else Update(k << 1 | 1, m + 1, r, u, v);
    IT[k] = max(IT[k << 1], IT[k << 1 | 1]);
}

int Query(int k, int l, int r, int u, int v) {
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return IT[k];
    int m = (l + r) >> 1;
    return max(Query(k << 1, l, m, u, v), Query(k << 1 | 1, m + 1, r, u, v));
}

int root(int u) { return (kount[u] < 0 ? u : kount[u] = root(kount[u])); }
void Union(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return;
    int t = kount[u] + kount[v];
    if (kount[u] > kount[v]) swap(u, v);
    kount[u] = t;
    kount[v] = u;
    rightMost[u] = max(rightMost[u], rightMost[v]);
}

int main() {

    int n, d;
    cin >> n >> d;
    int ans = 0;
    vector<int> Rank;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        perm[i] = i;
    }
    sort(perm + 1, perm + n + 1, [](int x, int y) {
        return a[x] != a[y] ? a[x] < a[y] : x > y;
    });

    set<int> obtacles;
    obtacles.insert(0);
    for (int i = 1; i <= n; ++i) kount[i] = -1, rightMost[i] = i;
    for (int i = n; i > 0; --i) {
        int id = perm[i];
        leftMost[id] = *(--obtacles.lower_bound(id));
        if (id > 1  && a[id - 1] >= a[id]) Union(id - 1, id);
        if (id != n && a[id + 1] > a[id]) Union(id, id + 1);
        int r = root(id);
        if (-kount[r] >= d) {
            obtacles.insert(rightMost[r]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        int id = perm[i];
        int f = Query(1, 1, n, leftMost[id], id) + 1;
        ans = max(ans, f);
        Update(1, 1, n, id, f);
    }
    
    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void Update(int, int, int, int, int)':
Main.cpp:11:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     int m = l + r >> 1;
      |             ~~^~~

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