Submission #1207944

#TimeUsernameProblemLanguageResultExecution timeMemory
1207944BoomydayFinancial Report (JOI21_financial)C++20
100 / 100
674 ms86700 KiB
// // Created by adavy on 5/26/2025. // #include <bits/stdc++.h> using namespace std; using ll = long long; int SSZ = 524288; vector<int> seg(2*SSZ, 0); void update(int i, int x){ i += SSZ; seg[i] = x; i /= 2; while(i > 0){ seg[i] = max(seg[2*i], seg[2*i + 1]); i /= 2; } } int query(int l, int r){ l += SSZ, r += SSZ; int ans = 0; while(l <= r){ if (l&1) ans = max(ans, seg[l++]); if(!(r&1)) ans = max(ans, seg[r--]); l /= 2; r /= 2; } return ans; } int main(){ int N, D; cin >> N >> D; vector<ll> nums(N); for(int i=0;i<N;++i){ cin >> nums[i]; } set<ll> coords(nums.begin(), nums.end()); map<ll, int> coord_map; int idx = 0; for(auto x : coords){ coord_map[x] = idx++; } vector<vector<int>> blockends(N), inds(N); for(int i=0;i<N;++i){ nums[i] = coord_map[nums[i]]; inds[nums[i]].push_back(i); } multiset<int> curblock; for(int i=N-D+1;i<N;++i) { curblock.insert(nums[i]); } for(int i = N-D;i>=0;--i){ curblock.insert(nums[i]); int minnum = *curblock.begin(); blockends[minnum].push_back(i + D - 1); curblock.erase(curblock.find(nums[i + D - 1])); } set<int> blocks = {N-1}; for(int i=N-1;i>=0;--i){ for(auto&ind:inds[i]){ int right = min(ind+D, N-1); int next_end = *blocks.lower_bound(right); update(ind, 1 + query(ind, next_end)); } for(auto&x:blockends[i]) { blocks.insert(x); } } cout << query(0, N-1) << endl; }
#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...