Submission #1194976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194976		badge881	Bouquet (EGOI24_bouquet)	C++20	100 / 100	166 ms	31212 KiB

Main

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

#define int long long

const int maxn = 2e5 + 5;

int st[4 * maxn];

void update(int id, int l, int r, int i, int val)
{
    if (l > i || r < i || l > r)
        return;

    if (l == r)
    {
        st[id] = max(st[id], val);
        return;
    }

    int mid = (l + r) / 2;

    update(2 * id, l, mid, i, val);
    update(2 * id + 1, mid + 1, r, i, val);

    st[id] = max(st[2 * id], st[2 * id + 1]);
}

int get(int id, int l, int r, int x, int y)
{
    if (l > y || r < x)
        return 0;
    if (l >= x && r <= y)
        return st[id];

    int mid = (l + r) / 2;

    return max(get(2 * id, l, mid, x, y), get(2 * id + 1, mid + 1, r, x, y));
}

signed main()
{
    int n;
    scanf("%lld", &n);
    vector<int> a(n + 1), b(n + 1), sweep1[n + 2], sweep2[n + 2];

    for (int i = 1; i <= n; i++)
    {
        scanf("%lld %lld", &a[i], &b[i]);
        sweep1[min(i + b[i], n) + 1].push_back(i);
        sweep2[i].push_back(max(1ll, i - a[i]) - 1);
    }

    vector<int> dp(n + 1, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j : sweep1[i])
            update(1, 1, n, j, dp[j]);
        for (int j : sweep2[i])
        {
            dp[i] = max(dp[i], get(1, 1, n, 1, j) + 1);
            ans = max(ans, dp[i]);
        }
    }

    printf("%lld\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld %lld", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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