Submission #1227324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227324		acoatoitgs	Bouquet (EGOI24_bouquet)	C++20	8 / 100	156 ms	102296 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll long long
#define pb push_back
#define m_pi 2 * acos(0.0)
#define all(a) (a).begin(), (a).end()
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
void solve();

constexpr bool isTc = 0;
int main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    if (isTc)
    {
        int T;
        cin >> T;
        while (T--)
        {
            solve();
        }
    }
    else
        solve();
    return 0;
}

/*######################################*/
ll N;
vector<ll> L, R;


struct Node
{
    Node* left, *right;
    ll value;
};

using nptr = Node*;
Node pool[5'000'000];
int ij = 0;
nptr getNode()
{
    return &(pool[ij++] = Node());
}

void build(nptr node, ll l, ll r)
{
    if(l == r) return;
    node->left = getNode();
    node->right = getNode();

    ll mid = (l+r)/2;
    build(node->left, l, mid);
    build(node->right, mid+1, r);
}

ll query(nptr node, ll l, ll r, ll tl, ll tr)
{
    if(l >= tl && r <= tr) return node->value;
    if(l > tr || r < tl) return 0;

    ll mid = (l+r)/2;
    return  max(query(node->left, l, mid, tl, tr), 
            query(node->right, mid+1, r, tl, tr));
}

void update(nptr node, nptr vers, ll l, ll r, ll t, ll v)
{
    // cout << l << " " << r << " " << t << " " << v << "\n";
    if(l == r)
    {
        assert(l == t);
        vers->value = max(node->value, v);
        node->value = max(node->value, v);
        return;
    }

    ll mid = (l+r)/2;
    if(t <= mid) 
    {
        vers->left = getNode();
        vers->right = node->right;
        update(node->left, vers->left, l, mid, t, v);
    }
    else 
    {
        vers->right = getNode();
        vers->left = node->left;
        update(node->right, vers->right, mid+1, r, t, v);
    }

    vers->value = max(vers->left->value, vers->right->value);
}

ll query(nptr node, ll l, ll r)
{
    if(r < 0 || l > N) return 0; 
    if(l > r) return 0;

    l = max(l, 0ll);
    r = min(r, N);

    return query(node, 0, N, l, r);
}

void solve()
{
    cin >> N;
    L.resize(N);
    R.resize(N);
    for(int i = 0; i < N; i++) cin >> L[i] >> R[i];
    
    nptr st = getNode();
    build(st, 0, N);
    vector<nptr> vers(N);

    for(ll i = 0; i < N; i++)
    {
        // cout << "\nTulip: " << i << "\n";
        // cout << "Query: " << 0 << " " << i-L[i]-1 << " -> " << query(st, 0, i-L[i]-1) << "\n";
        // cout << "Update: " << i+R[i] << "\n";

        vers[i] = getNode();
        ll tv = i-L[i]-1;
        if(tv < 0) 
        {
            update(st, vers[i], 0, N, min(i+R[i], N), 1);
            continue;
        }

        ll q = query(vers[tv], 0, i-1);
        update(vers[tv], vers[i], 0, N, min(i+R[i], N), 1+q);
    }   
    ll ans = 0;
    for(auto v : vers) ans = max(ans, query(v, 0, N));
    cout << ans << "\n";
}

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