# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1209082 | matthew | Bouquet (EGOI24_bouquet) | C++20 | 77 ms | 14548 KiB |
#include <stdio.h>
#include <algorithm>
#include <vector>
const int MAX_N = 2e5;
struct AIB {
int n;
int aib[MAX_N + 1];
void init(int _n) { n = _n; }
int query_max(int pref) {
int res = 0;
for(; pref > 0; pref &= pref - 1) {
res = std::max(res, aib[pref]);
}
return res;
}
void update(int pos, int val) {
for(; pos <= n; pos += pos & -pos) {
aib[pos] = std::max(aib[pos], val);
}
}
};
int l[MAX_N], r[MAX_N];
AIB aib;
std::vector<int> updates[MAX_N + 1];
int dp[MAX_N];
void clamp_max(int &val, int max) {
if(val > max) {
val = max;
}
}
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d", &l[i], &r[i]);
clamp_max(l[i], i);
clamp_max(r[i], n - 1 - i);
}
aib.init(n);
int res = 0;
for(int i = 0; i < n; i++) {
for(int x : updates[i]) {
aib.update(x + 1, dp[x]);
}
int leftb = i + 1 - l[i];
dp[i] = 1 + aib.query_max(leftb - 1);
if(dp[i] > res) {
res = dp[i];
}
updates[i + r[i] + 1].push_back(i);
}
printf("%d\n", res);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |