Submission #564533

#	Time	Username	Problem	Language	Result	Execution time	Memory
564533		nikatamliani	Financial Report (JOI21_financial)	C++14	0 / 100	4094 ms	19496 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
// void compress(vector<int*> &v) {
//     int prv = -1, cnt = 0;
//     sort(v.begin(), v.end(), [&](int* a, int* b) {
//         return *a < *b;
//     });
//     for (int i = 0; i < (int)v.size(); ++i) {
//         cnt += prv < *v[i];
//         prv = *v[i];
//         *v[i] = cnt;
        
//     }
// }
vector<int> ids[N], to_delete[N];
int n, d;
int a[N], on[N], rgh[N], p[N], s[N], dp[N], t[4 * N];
// int find_set(int x) {
//     return p[x] == x ? x : p[x] = find_set(p[x]);
// } 
// void union_sets(int u, int v) {
//     u = find_set(u);
//     v = find_set(v);
//     if (u == v) {
//         return;
//     }
//     if (u > v) {
//         swap(u, v);
//     }
//     p[v] = u; 
//     s[u] += s[v];
// }
// void update(int l, int r, int x, int v, int pos) {
//     if (l > x || r < x) {
//         return;
//     }
//     if (l == r) {
//         t[pos] = v;
//     } else {
//         int m = l + r >> 1;
//         update(l, m, x, v, pos << 1);
//         update(m+1, r, x, v, pos << 1 | 1); 
//         t[pos] = max(t[pos << 1], t[pos << 1 | 1]);  
//     }
// }
// void update(int id, int v) {
//     update(1, n, id, v, 1);
// }
// int query(int l, int r, int L, int R, int pos) {
//     if (L > r || l > R) return 0;
//     if (L <= l && R >= r) {
//         return t[pos];
//     }
//     int m = l + r >> 1;
//     return max(query(l, m, L, R, pos << 1), query(m + 1, r, L, R, pos << 1 | 1));
// }
// int query(int l, int r) {
//     return query(1, n, l, r, 1);
// }
// multiset<int> m[N];
// void del(int id, int v) {
//     m[id].erase(m[id].find(v));
// }
// void ins(int id, int v) {
//     m[id].insert(v);
// }
// int get(int id) {
//     if (!m[id].empty()) {
//         return *m[id].rbegin();
//     }
//     return 0;
// }
int main() {
    cin >> n >> d;
    // vector<int*> coords(n);
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        s[i] = 1;
        cin >> a[i];
        // coords[i - 1] = &a[i];
    }
    // compress(coords);
    // for (int i = n; i >= 1; --i) {
    //     ids[a[i]].push_back(i);
    // }
    // set<int> st = {n + 1}; 
    // for (int i = n; i >= 1; --i) {
    //     for (int id : ids[i]) {
    //         rgh[id] = min(*st.lower_bound(id) + d - 1, n);
    //         on[id] = 1;
    //         if (on[id + 1] == 1) {
    //             union_sets(id, id + 1);
    //         }
    //         if (on[id - 1] == 1) {
    //             union_sets(id, id - 1); 
    //         }
    //         int u = find_set(id);
    //         if (s[u] >= d) {
    //             st.insert(u);
    //         }
    //     }
    // }
    for (int i = 1; i <= n; ++i) {
        int count = 0;
        rgh[i] = n;
        for (int j = i + 1; j <= n; ++j) {
            if (count == d) break;
            rgh[i] = j;
            if (a[j] >= a[i]) {
                ++count;
            } else {
                count = 0;
            }
        }
    }
    int best = 0;
    rgh[0] = n;
    for (int i = 1; i <= n; ++i) {
        // dp[i] = query(1, a[i] - 1) + 1;
        // ins(a[i], dp[i]);
        // update(a[i], get(a[i]));
        // for (int id : to_delete[i]) {
        //     del(a[id], dp[id]);
        //     update(id, get(a[id])); 
        // }
        for (int j = 0; j < i; ++j) {
            if (rgh[j] >= i && a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        best = max(best, dp[i]);
    }
    cout << best << endl;
}

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