제출 #1162596

#제출 시각아이디문제언어결과실행 시간메모리
1162596LucppBouquet (EGOI24_bouquet)C++20
100 / 100
62 ms19964 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define sz(x) (int)size(x) #define all(x) (x).begin(), (x).end() int n; vector<int> seg; int qry(int l, int r){ l += n, r += n; 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; } void upd(int i, int x){ seg[i += n] = x; for(i/=2; i; i/=2) seg[i] = max(seg[2*i], seg[2*i+1]); } void solve(){ cin >> n; seg.resize(2*n); vector<int> l(n), r(n); for(int i = 0; i < n; i++) cin >> l[i] >> r[i]; vector<int> dp(n); vector<vector<int>> events(2*n); for(int i = 0; i < n; i++){ dp[i] = qry(0, i-l[i]) + 1; events[i+r[i]].push_back(i); for(int j : events[i]) upd(j, dp[j]); } cout << *max_element(all(dp)) << "\n"; } int main(){ cin.tie(0)->sync_with_stdio(false); solve(); }
#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...