Submission #1170797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170797		nguyenkhangninh99	Bouquet (EGOI24_bouquet)	C++20	100 / 100	122 ms	31156 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 2e5 + 5;

int st[4 * maxn];

void update(int id, int l, int r, int i, int val){
    if (l > i || r < i || l > r) return;
 
    if (l == r){
        st[id] = max(st[id], val);
        return;
    }
 
    int mid = (l + r) / 2;

    update(2 * id, l, mid, i, val);
    update(2 * id + 1, mid + 1, r, i, val);
 
    st[id] = max(st[2 * id], st[2 * id + 1]);
}
 
 
int get(int id, int l, int r, int x, int y){
    if(l > y || r < x) return 0;
    if(l >= x && r <= y) return st[id];
 
    int mid = (l + r) / 2;
 
    return max(get(2 * id, l, mid, x, y), get(2 * id + 1, mid + 1, r, x , y));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<int> a(n + 1), b(n + 1), sweep1[n + 2], sweep2[n + 2];
  
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        sweep1[min(i + b[i], n) + 1].push_back(i);
        sweep2[i].push_back(max(1ll, i - a[i]) - 1);
    }
  
    vector<int> dp(n + 1, 1);
    for(int i = 1; i <= n; i++){
        for(int j: sweep1[i]) update(1, 1, n, j, dp[j]);
        for(int j: sweep2[i]) dp[i] = max(dp[i], get(1, 1, n, 1, j) + 1);
    }
  
    cout << *max_element(dp.begin(), dp.end());
}

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