Submission #1317511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317511		haithamcoder	Bouquet (EGOI24_bouquet)	C++20	24 / 100	86 ms	28388 KiB

Main

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

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;

#define f first
#define s second

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

struct segtree {
    ll n;
    vector<ll> tree;

    segtree(ll N) {
        n = N;
        tree.assign(2 * n, 0);
    }

    void update(ll p, ll x) {
        p += n;
        tree[p] = x;

        for (p >>= 1; p > 0; p >>= 1) {
            tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
        }
    }
    ll mx(ll l, ll r) {
        ll res = 0;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++]);
            if (!(r & 1)) res = max(res, tree[r--]);
        }
        return res;
    }
};

int main() {
    Algerian OI

    ll n;
    cin >> n;
    vector<pll> a(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].f >> a[i].s;
        a[i].f = min(a[i].f, i - 1);
        a[i].s = min(a[i].s, n - i);
    }

    vector<vector<ll>> dp(n + 1, vector<ll>(2));

    vector<vector<ll>> update(n + 1);

    for (ll i = 1; i <= n; i++) {
        ll l = i - a[i].f;
        update[l - 1].push_back(i);
    }

    segtree seg(n + 1);

    for (ll i = 0; i <= n; i++) {
        seg.update(i + a[i].s, dp[i][1]);
        if (i > 0) dp[i][0] = max(dp[i][0], max(dp[i - 1][0], dp[i - 1][1]));
        // dbg(dp[i]);
        // if (i < n) dp[i + 1] = max(dp[i + 1], dp[i]);
        for (ll x : update[i]) {
            dp[x][1] = max(dp[x][1], seg.mx(0, x - 1) + 1);
        }
    }

    cout << max(dp[n][1], dp[n][0]) << "\n";

    return 0;
}

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