Submission #1093356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093356		kem	Bouquet (EGOI24_bouquet)	C++14	100 / 100	56 ms	21076 KiB

Main

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

#define NAME "name"

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

const int LIM = 5e5 + 3;
const int INF = 1e9;
const int mod = 1e9 + 7;

int n, l, r;
vector<pii> upd[LIM];
int bit[LIM];
int ans = 1;

void update(int idx, int val)
{
    for (; idx < LIM; idx = idx | (idx + 1))
        bit[idx] = max(bit[idx], val);
}

int get(int idx)
{
    int res = 0;
    for (; idx >= 0; idx = (idx & (idx + 1)) - 1)
        res = max(res, bit[idx]);
    return res;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (ifstream(NAME ".inp"))
    {
        freopen(NAME ".inp", "r", stdin);
        freopen(NAME ".out", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (auto v : upd[i])
            update(v.fi, v.se);

        cin >> l >> r;

        int res = get(i - l - 1) + 1;
        ans = max(ans, res);
        if (i + r + 1 <= n)
            upd[i + r + 1].pb({i, res});
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(NAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(NAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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