Submission #521720

#TimeUsernameProblemLanguageResultExecution timeMemory
521720surguttiFinancial Report (JOI21_financial)C++17
5 / 100
299 ms21068 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); int n, d; cin >> n >> d; vector<int> a(n); for (int &x : a) cin >> x; vector<int> v = a; v.push_back(-1); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin(); int tree_size = 1; while (tree_size < (int) v.size()) tree_size <<= 1; vector<int> tree(tree_size << 1); auto query = [&tree, tree_size] (int l, int r) { int res = 0; for (l += tree_size, r += tree_size + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) res = max(res, tree[l++]); if (r & 1) res = max(res, tree[--r]); } return res; }; int ans = 0; auto update = [&tree, tree_size, &ans] (int p, int v) { ans = max(ans, v); for (tree[p += tree_size] = v; p >>= 1; ) tree[p] = max(tree[p << 1 | 0], tree[p << 1 | 1]); }; set<pair<int, int>> between, past; for (int i = 0; i < n; i++) { update(a[i], query(0, a[i] - 1) + 1); between.insert({a[i], i}); if (i >= d) { between.erase({a[i - d], i - d}); past.insert({a[i - d], i - d}); while (past.size() && between.begin()->first > past.begin()->first) { update(past.begin()->first, 0); past.erase(past.begin()); } } } cout << ans << '\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...