제출 #1228924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228924		Rokas159	Bouquet (EGOI24_bouquet)	C++20	24 / 100	138 ms	19280 KiB

Main

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

#define int long long
#define endl '\n'

const int MAXN = 2e5+10;

int l[4*MAXN], r[4*MAXN], lazyAdd[4*MAXN], lazySet[4*MAXN], val[4*MAXN], a[MAXN];

int currInd = 0;

int n;

void build(int v = 1) {
    lazySet[v] = 0;
    lazyAdd[v] = 0;
    if (v < n+1) {
        build(v*2);
        build(v*2+1);
        l[v] = l[v*2];
        r[v] = r[v*2+1];
        val[v] = max(val[v*2],val[v*2+1]);
    } else {
        l[v] = currInd;
        r[v] = currInd;
        val[v] = 0;
        currInd++;
    }
}

void pushLazy(int v) {
    if (lazySet[v] != 0) {
        val[v*2] = lazySet[v];
        val[v*2+1] = lazySet[v];

        lazySet[v*2] = lazySet[v];
        lazySet[v*2+1] = lazySet[v];

        lazyAdd[v*2] = 0;
        lazyAdd[v*2+1] = 0;

        lazySet[v] = 0;
    }

    val[v*2] += lazyAdd[v];
    val[v*2+1] += lazyAdd[v];

    lazyAdd[v*2] += lazyAdd[v];
    lazyAdd[v*2+1] += lazyAdd[v];

    lazyAdd[v] = 0;
}

void updateSum(int L, int R, int x, int v = 1) {
    if (R < l[v] || r[v] < L) {
        return;
    } else if (L <= l[v] && r[v] <= R) {
        lazyAdd[v] += x;
        val[v] += x;
    } else {
        pushLazy(v);

        updateSum(L,R,x,v*2);
        updateSum(L,R,x,v*2+1);
        val[v] = max(val[v*2],val[v*2+1]);
    }
}

void updateSet(int L, int R, int x, int v = 1) {
    if (R < l[v] || r[v] < L) {
        return;
    } else if (L <= l[v] && r[v] <= R) {
        lazyAdd[v] = 0;
        lazySet[v] = x;
        val[v] = x;
    } else {
        pushLazy(v);

        updateSet(L,R,x,v*2);
        updateSet(L,R,x,v*2+1);
        val[v] = max(val[v*2],val[v*2+1]);
    }
}

int query(int L, int R, int v = 1) {
    if (R < l[v] || r[v] < L) {
        return 0;
    } else if (L <= l[v] && r[v] <= R) {
        return val[v];
    } else {
        pushLazy(v);
        return max(query(L,R,v*2),query(L,R,v*2+1));
    }
}

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

    cin >> n;

    int l[n], r[n];

    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];

        
    }

    build();

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        int newDP = max(query(0, i-l[i-1]-1) + 1, query(i-1, i-1));


        updateSet(i, i, newDP);
        ans = max(ans, newDP);
    }

    cout << ans << endl;

    cout.flush();
    return 0;
}

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