Submission #1226554

#TimeUsernameProblemLanguageResultExecution timeMemory
1226554overwatch9Financial Report (JOI21_financial)C++20
100 / 100
418 ms23896 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 1; struct stree { #define lc v*2 #define rc v*2+1 vector <int> tree; stree (int s) { tree.resize(s*4, 0); } void pushup(int v) { tree[v] = max(tree[lc], tree[rc]); } void update(int v, int tl, int tr, int p, int val) { if (tl > p || tr < p) return; if (tl == tr) { tree[v] = val; return; } int tm = (tl + tr) / 2; update(lc, tl, tm, p, val); update(rc, tm+1, tr, p, val); pushup(v); } int query(int v, int tl, int tr, int l, int r) { if (tl > r || tr < l) return -1; if (tl >= l && tr <= r) return tree[v]; int tm = (tl + tr) / 2; int a = query(lc, tl, tm, l, r); int b = query(rc, tm+1, tr, l, r); return max(a, b); } }; bool comp(pair <int, int> a, pair <int, int> b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; } int last[maxn]; int head(int x) { if (x == last[x]) return x; return last[x] = head(last[x]); } void connect(int a, int b) { a = head(a); b = head(b); if (a != b) { if (a > b) swap(a, b); last[b] = a; } } int main() { int n, d; cin >> n >> d; vector <pair <int, int>> nums(n); for (int i = 0; i < n; i++) { last[i] = i; cin >> nums[i].first; nums[i].second = i; } sort(nums.begin(), nums.end(), comp); vector <int> dp(n); stree tree(n); set <int> ids; for (int i = 0; i < n; i++) { int id = nums[i].second; auto it = ids.upper_bound(id); if (it != ids.end()) { if (*it - id <= d) connect(*it, id); } if (it != ids.begin()) { it--; if (id - *it <= d) connect(*it, id); } int st = head(id); dp[id] = tree.query(1, 0, n, st, id) + 1; tree.update(1, 0, n, id, dp[id]); ids.insert(id); } cout << *max_element(dp.begin(), dp.end()) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...