Submission #1248064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248064		mosesmayer	Bouquet (EGOI24_bouquet)	C++20	100 / 100	75 ms	6328 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

template<class T> inline T re(){
    T N = 0; char c = getchar(); bool neg = 0;
    for (; c < '0' || c > '9'; c = getchar()) neg |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        N = (N<<3)+(N<<1) + c - '0';
    return neg ? -N : N;
}

const int MX = 2e5;

int n;
int l[MX + 5], r[MX + 5];

int dp[MX + 5];

namespace SegTree {
    int st[MX * 4 + 50];
    void upd(int pos, int x, int p = 1, int l = 0, int r = n) {
        if (l == r) return void(st[p] = x);
        int md = (l + r) >> 1;
        if (pos <= md) upd(pos, x, p << 1, l, md);
        else upd(pos, x, p << 1 | 1, md + 1, r);
        st[p] = max(st[p << 1], st[p << 1 | 1]);
    }
    int get(int i, int j, int p = 1, int l = 0, int r = n) {
        if (i > j || j < l || i > r) return 0;
        if (i <= l && j >= r) return st[p];
        int md = (l + r) >> 1;
        return max(get(i, j, p << 1, l, md), get(i, j, p << 1 | 1, md + 1, r));
    }
};
using namespace SegTree;

priority_queue<pii, vector<pii>, greater<pii>> pq;

int main() {
    n = re<int>();
    for (int i = 1; i <= n; i++) {
        l[i] = re<int>(); r[i] = re<int>();
    }
    
    dp[0] = 0;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        while (!pq.empty() && pq.top().fi < i) {
            int x = pq.top().se; pq.pop();
            upd(x, dp[x]);
        }
        dp[i] = 1;
        dp[i] = max(dp[i], get(0, i - l[i] - 1) + 1);
        /*
        for (int j = i - l[i] - 1; j > 0; --j) {
            if (j + r[j] < i) dp[i] = max(dp[i], dp[j] + 1);
        }
        */
        mx = max(mx, dp[i]);
        pq.emplace(i + r[i], i);
    }
    printf("%lld\n", mx);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:69:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
   69 |     printf("%lld\n", mx);
      |             ~~~^     ~~
      |                |     |
      |                |     int
      |                long long int
      |             %d

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