Submission #1229270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229270		Harold	Bouquet (EGOI24_bouquet)	C++20	42 / 100	107 ms	7868 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

const int MAXN = 2e5+1;
// Intervalų medžio implementacija (pavyzdys).
// Šis intervalų medis palaiko dviejų tipų operacijas:
// 1) Atnaujinti masyvo p-tojo elemento reikšmę į x. 
// 2) Rasti sumą masyvo elementų nuo x-ojo iki y-ojo. 

struct node {
    // Viršūnė gali saugoti ir daugiau (ar kitokias) reikšmių - 
    // priklauso nuo uždavinio ir kokių operacijų reikia.
    long long mx;   
} tree[4*MAXN]; // viršūnių masyvas - svarbu, jog būtų 4 kartus daugiau viršūnių
// Medžio viršūnė tree[id] turi du vaikus: tree[2*id] ir tree[2*id + 1]
// Jei medžio viršūnė tree[id] aprėpia intervalą [l, r], tai kairysis vaikas aprėpia
// intervalą [l, mid], o dešinysis - intervalą [mid+1, r], kur mid = (l+r) / 2.
// Medžio šaknis yra tree[1].

int n, q;

// Nustatomos pradinės medžio reikšmės. Priklausomai nuo uždavinio ir implementacijos, ši funkcija nebūtina.
// Šią funkciją iškviesti: build().
// Parametrai: id - viršūnės numeris, l ir r - intervalas, kurį aprėpia viršūnė.
void build(int id=1, int l=1, int r=n) {
    if (l == r) {
        // Esame intervalų medžio lape, kuris aprėpia tik vieną masyvo elementą: l-tąjį.
        tree[id].mx = 0;
        return;
    }

    int mid = (l+r) / 2;
    build(2*id, l, mid); // kairysis pomedis
    build(2*id + 1, mid + 1, r); // dešinysis pomedis
    tree[id].mx = max(tree[2*id].mx, tree[2*id+1].mx);
}

// Atnaujinama masyvo p-oji reikšmė į reikšmę x.
// Kviesti: update(p, x).
void update(int p, long long x, int id=1, int l=1, int r=n) {
    if (l == r) {
        // Esame intervalų medžio lape, tad pasiekėme reikiamą viršūnę.
        tree[id].mx += x; // atnaujiname į naują reikšmę
        return;
    }

    int mid = (l+r) / 2;
    if (p <= mid) // jeigu kairysis vaikas aprėpia intervalą, kuriame yra ir p
        update(p, x, 2*id, l, mid);
    else // kitu atveju, dešinysis vaikas aprėpia intervalą, kuriame yra ir p
        update(p, x, 2*id+1, mid+1, r);

    tree[id].mx = max(tree[2*id].mx, tree[2*id+1].mx);
}

// Randama suma intervalo [x, y].
// Kviesti: getSum(x, y).
int getMax(int x, int y, int id=1, int l=1, int r=n) {
    if (l > y || r < x) 
        // Dabartinė viršūnė nekerta intervalo [x, y]. 
        return 0;
    if (x <= l && r <= y)
        return tree[id].mx;

    int mid = (l+r) / 2;
    return max(getMax(x, y, 2*id, l, mid), getMax(x, y, 2*id+1, mid+1, r));
}

int main() {
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    
    vector<int> dp(n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
    dp[0] = 1;
    q.push({a[0].second+1, 1});
    
    build();
    for (int i = 1; i < n; i++)
    {
        while(!q.empty()) {
            if(q.top().first > i) {
                break;
            }
            update(q.top().second, dp[q.top().second-1]);
            q.pop();
        }

        dp[i] = (i-a[i].first-1 >= 0 ? 1+getMax(1, i-a[i].first) : 0);
        q.push({i+a[i].second+1, i+1});
    }

    int mx = 0;
    for (int i = 0; i < n; i++)
    {
        mx = max(mx, dp[i]);
    }
    
    cout << mx << endl;
    
    return 0;
}

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