Submission #1267504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267504		nekolie	Bouquet (EGOI24_bouquet)	C++20	100 / 100	56 ms	13688 KiB

Main

// Suzune, if you want to ascend to a higher class, struggle with every ounce of strenght you have.
#include <bits/stdc++.h>
using namespace std;

const int baza = (1<<18), M = 200000;
int n,l,r, dp[M], d[2*baza];
vector<int> upd[M];
void akt(int i) {
    i = (i+baza)/2;
    while (i > 0)
        d[i] = max(d[2*i],d[2*i+1]), i >>= 1;
}
int maks(int a, int b) {
    int w = 0; a += baza-1, b += baza+1;
    while (a/2 != b/2) {
        if ((a&1) == 0)
            w = max(w,d[a+1]);
        if ((b&1) == 1)
            w = max(w,d[b-1]);
        a >>= 1, b >>= 1;
    }
    return w;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        for (int j : upd[i])
            d[j+baza] = dp[j], akt(j);
        dp[i] = 1 + ((i-l > 0) ? maks(0,i-l-1) : 0);
        if (i+r+1 < n)
            upd[i+r+1].push_back(i);
    }
    cout << *max_element(dp,dp+M) << endl;
    return 0;
}

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