Submission #1229255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229255		Harold	Bouquet (EGOI24_bouquet)	C++20	24 / 100	156 ms	9916 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> dp1(n), dp2(n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q1, q2;
    
    dp1[0] = 1;
    if(a[0].second+1 < n) {
        q1.push({a[0].second+1, 1});
    } 
    dp2[n-1] = 1;
    if(n-1-a[n-1].first-1 >= 0) {
        q2.push({n-1-a[n-1].first-1, n});
    }
    
    build();
    for (int i = 1; i < n; i++)
    {
        while(!q1.empty()) {
            if(q1.top().first > i) {
                break;
            }
            update(q1.top().second, dp1[q1.top().second-1]);
            q1.pop();
        }

        dp1[i] = max(dp1[i-1], (i-a[i].first-1 >= 0 ? 1+getMax(1, i-a[i].first) : 0));
        if(i+a[i].second+1 < n) {
            q1.push({i+a[i].second+1, i+1});
        }
    }

    build();
    for (int i = n-2; i >= 0; i--)
    {
        while(!q2.empty()) {
            //cout << q2.top().first << i << endl;
            if(q2.top().first < i) {
                break;
            }
            update(q2.top().second, dp2[q2.top().second-1]);
            //cout << q2.top().second << "mm ";
            q2.pop();
        }
        /*for (int k = 0; k < 2*n; k++)
        {
            cout << tree[k].mx << " ";
        }*/

        //cout << endl;

        dp2[i] = max(dp2[i+1], (i+a[i].second+1 < n ? 1+getMax(i+a[i].second+2, n) : 0));
        if(i-a[i].first-1 >= 0) {
            q2.push({i-a[i].first-1, i+1});
        }
    }

    /*for(auto i: dp1) {
        cout << i << " ";
    }
    cout << endl;

    for(auto i: dp2) {
        cout << i << " ";
    }
    cout << endl;*/

    cout << max(dp1[n-1], dp2[0]) << endl;
    
    return 0;
}

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