| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 635899 | Bruteforceman | Financial Report (JOI21_financial) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 1; i <= n; ++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) { to_delete[rgh[i]].push_back(i); } 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])); } best = max(best, dp[i]); } cout << best << endl;}