제출 #1235978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235978		asdfghqwert	Bouquet (EGOI24_bouquet)	C++20	100 / 100	55 ms	14480 KiB

Main

    #pragma GCC optimize("O3,Ofast")
#include <bits/stdc++.h>
//define int long long
using namespace std;
    const int MOD  = 1e9 + 7;
struct FENWICK{
    vector<int> a;
    int n;
    FENWICK(int _n){
        n = _n;
        a.resize(n + 1);
    }
    void update(int idx , int val){
        for(;idx <= n ; idx += idx & -idx)a[idx] = max(a[idx] , val);
    }
    int query(int idx){
        int ans = 0;
        for(;idx > 0;idx -= idx & -idx)ans = max(ans , a[idx]);
        return ans;
    }
};
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , ans = 0;
    cin >> n;
    FENWICK fen(n + 1);
    vector<int> pen_val(n + 1);
    vector<pair<int , int>> segment(n + 1);
    vector<vector<int>> segmentF(n + 1);
    for(int i = 1 ; i <= n ; i++){
        cin >> segment[i].first >> segment[i].second;
        segment[i].first = max(1 , i - segment[i].first);
        segment[i].second = min(n , i + segment[i].second);
        segmentF[segment[i].second].push_back(i);
    }
    for(int i = 1 ; i <= n ; i++){
        pen_val[i] = fen.query(segment[i].first - 1) + 1;
        ans = max(ans , pen_val[i]);
        for(int j : segmentF[i]){
            fen.update(j , pen_val[j]);
        }
    }
    cout << ans;
}

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