제출 #1167746

#제출 시각아이디문제언어결과실행 시간메모리
1167746tsengangBouquet (EGOI24_bouquet)C++20
100 / 100
128 ms22260 KiB
#include <bits/stdc++.h> #define ll long long #define ff first #define ss second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pb push_back #define ertunt return #define vodka void using namespace std; struct segtree{ ll n; vector<ll>d; segtree(ll n): n(n){ d.resize(4*n); build(1,1,n); } vodka build(ll v, ll l, ll r){ if(l == r){ d[v] = 0; ertunt; } ll m = (l+r)/2; build(v*2,l,m); build(v*2+1,m+1,r); d[v] = max(d[v*2],d[v*2+1]); } vodka update(ll v,ll l, ll r, ll pos, ll val){ if(pos < l or pos > r)ertunt; if(l == r){ d[v] = max(d[v],val); ertunt; } ll m = (l+r)/2; update(v*2,l,m,pos,val); update(v*2+1,m+1,r,pos,val); d[v] = max(d[v*2],d[v*2+1]); } ll query(ll v, ll l, ll r, ll L, ll R){ if(R < l || r < L) ertunt 0ll; if(L<=l&&r<=R) ertunt d[v]; ll m = (l+r)/2; ertunt max(query(v*2,l,m,L,R),query(v*2+1,m+1,r,L,R)); } }; int main() { ll n; cin >> n; ll l[n+1],r[n+1]; vector<ll>dis[n+2]; for(ll i = 1; i <= n; i++){ cin >> l[i] >> r[i]; dis[min(i+r[i]+1,n+1)].pb(i); } segtree gang(n+1); vector<ll>dp(n+1,1); for(ll i = 1; i <= n; i++){ for(auto x : dis[i]){ gang.update(1,1,n+1,x,dp[x]); } dp[i] = gang.query(1,1,n+1,1,max(0ll,i-l[i]-1))+1; } cout << *max_element(all(dp)); }
#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...