Submission #1181113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181113		dusky	Bouquet (EGOI24_bouquet)	C++20	100 / 100	88 ms	15744 KiB

Main

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

int n, l[200005], r[200005], tree[1000005];
int cache[200005];

vector<int> toupdate[200005];

void update(int i, int x, int c = 1, int cl = 1, int cr = n) {
    if (cl == cr) { tree[c] = x; return; }
    int mid = (cl+cr)/2;
    if (i <= mid) update(i, x, c*2, cl, mid);
    else update(i, x, c*2+1, mid+1, cr);
    tree[c] = max(tree[c*2], tree[c*2+1]);
}
 
int query(int l, int r, int c = 1, int cl = 1, int cr = n) {
    if (l <= cl && cr <= r) return tree[c];
    int mid = (cl+cr)/2, ans = 0;
    if (l <= mid) ans = max(ans, query(l, r, 2*c, cl, mid));
    if (r > mid) ans = max(ans, query(l, r, 2*c+1, mid+1, cr));
    return ans;
}

int main() {
    // freopen("in.txt", "r", stdin);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &l[i], &r[i]);

    for (int i = 1; i <= n; i++) {
        cache[i] = 1;
        if (i-l[i]-1 >= 1) cache[i] = max(cache[i], query(1, i-l[i]-1) + 1);

        if (i + r[i] <= n) toupdate[i+r[i]].push_back(i);
        for (int j : toupdate[i]) update(j, cache[j]);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, cache[i]);
    printf("%d\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:29:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for (int i = 1; i <= n; i++) scanf("%d %d", &l[i], &r[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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