Submission #680995

#	Time	Username	Problem	Language	Result	Execution time	Memory
680995		jhwest2	Financial Report (JOI21_financial)	C++17	100 / 100	362 ms	15324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 303030;
int n, d, a[N], p[N], rr[N];

struct seg {
    int tree[N * 4];

    void update(int a, int v, int l, int r, int x) {
        if (l == r) {
            tree[x] = v;
            return;
        }
        int m = (l + r) / 2;
        if (a <= m)
            update(a, v, l, m, 2 * x);
        else 
            update(a, v, m + 1, r, 2 * x + 1);
        tree[x] = max(tree[2 * x], tree[2 * x + 1]);
    }
    int query(int a, int b, int l, int r, int x) {
        if (b < l || a > r)
            return 0;
        if (a <= l && r <= b)
            return tree[x];
        int m = (l + r) / 2;
        return max(query(a, b, l, m, 2 * x), query(a, b, m + 1, r, 2 * x + 1));
    }
} t1;

int par[N], sz[N], dp[N];
bool chk[N];

void init() {
    iota(par, par + N, 0);
}
int Find(int a) {
    return par[a] = ((par[a] == a) ? a : Find(par[a]));
}
void Union(int a, int b) {
    a = Find(a); b = Find(b);
    if (a != b) {
        par[b] = a;
        sz[a] += sz[b];
    }
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> d;
    vector<int> v;
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    
    for (int i = 1; i <= n; i++)
        p[i] = i;
    sort(p + 1, p + 1 + n, [&](auto i, auto j) {
        return a[i] > a[j];
    });

    init();
    set<int> st; // stores first positions for length >= d segments
    for (int i = 1, j = 1; i <= n; i = j) {
        while (j <= n && a[p[i]] == a[p[j]])
            ++j;

        // cout << i << ' ' << j << '\n';
        // for (int x : st)
        //     cout << x << ' ';
        // cout << "!\n";

        for (int k = i; k < j; k++) {
            auto it = st.lower_bound(p[k]);
            if (it == st.end())
                rr[p[k]] = n;
            else 
                rr[p[k]] = min(n, *it + d - 1);
        }

        for (int k = i; k < j; k++) {
            int x = p[k];
            chk[x] = 1;
            sz[x] = 1;
            if (d == 1)
                st.insert(x);

            if (x > 1 && chk[x - 1]) {
                int a = Find(x - 1);
                int b = Find(x);

                if (a != b) {
                    if (sz[b] >= d)
                        st.erase(b);

                    bool f = false;
                    if (sz[a] < d)
                        f = true;

                    Union(a, b);
                    if (f && sz[a] >= d)
                        st.insert(a);
                }
            }
            if (x < n && chk[x + 1]) {
                int a = Find(x);
                int b = Find(x + 1);

                if (a != b) {
                    if (sz[b] >= d) 
                        st.erase(b);
                    
                    bool f = false;
                    if (sz[a] < d)
                        f = true;

                    Union(a, b);
                    if (f && sz[a] >= d)
                        st.insert(a);
                }
            }
        }
    }
        
    for (int i = 1, j = 1; i <= n; i = j) {
        while (j <= n && a[p[i]] == a[p[j]])
            ++j;

        for (int k = i; k < j; k++) 
            dp[p[k]] = t1.query(p[k] + 1, rr[p[k]], 1, n, 1) + 1;
        for (int k = i; k < j; k++) 
            t1.update(p[k], dp[p[k]], 1, n, 1);
    }
    cout << *max_element(dp + 1, dp + 1 + 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