제출 #1148299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148299		Rafiullah	Bouquet (EGOI24_bouquet)	C++20	100 / 100	79 ms	20040 KiB

Main

#include<bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
#define int long long
const int N = 2e5+5;
const int mod = 1e9 + 7;
const int mod1 = 998244353;
const int LG = 20;
// #define s(i) (*s.find_by_order(i)) // Warning : Read this line.
int power(int b,int e){
    if(e<=0)return 1;
    int o = power(b,e>>1);
    o *= o, o %= mod1;
    if(e % 2)o *= b, o %= mod1;
    return o;
}
int val[N<<2];int n;
void update(int i,int x,int cur = 1,int st = 1,int en = n){
    val[cur] = max(val[cur] , x);
    if(st == en)return;
    int mid = (st + en) / 2;
    if(i <= mid)update(i,x,cur*2,st,mid);
    else update(i,x,cur*2+1,mid+1,en);
}
int get(int l,int r,int cur = 1,int st = 1,int en = n){
    if(l > r)return 0;
    if(l <= st and en <= r)return val[cur];
    if(en < l or r < st)return 0;
    int mid = (st + en) / 2;
    return max(get(l,r,cur*2,st,mid),get(l,r,cur*2+1,mid+1,en));
}
void solve(){
    cin >> n;
    vector<pair<int,int>> v(n + 1);
    for(int i = 1 ; i <= n ;i  ++){
        cin >> v[i].first >> v[i].second;
        v[i].first = min(v[i].first, i - 1);
        v[i].second = min(v[i].second, n - i );
    }
    vector<vector<int>> ids(n + 1);vector<int> dp(n + 1);
    for(int i = 1 ; i <= n ; i ++){
        dp[i] = 1 + get(1,i-v[i].first-1);
        ids[i+v[i].second].push_back(i);
        for(int Id : ids[i])
            update(Id, dp[Id]);
    }
    int ans = 0;
    for(int i = 0 ; i <= n ; i ++)ans=max(ans,dp[i]);
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30