Submission #1228573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228573		Rifal	Bouquet (EGOI24_bouquet)	C++20	100 / 100	80 ms	6520 KiB

Main

#include <bits/stdc++.h>
#include <fstream>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define pb push_back
#define INF 20000000000
#define fi first
#define se second
//#define cin fin
//#define cout fout
using namespace std;
//ofstream fout("input.txt");
//ifstream fin("output.txt");
//double const EPS = 1e-14;
typedef long long ll;
//const ll P = 10007;
const ll mod = 1e9 + 7;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int Max = 2e5 + 5;
int seg[Max*4], sol[Max];
int n;
pair<int,int> arr[Max];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
void Update(int x, int l, int r, int pos, int val) {
    if(l == r) {
        seg[x] = val;
    }
    else {
        int mid = (l+r)/2;
        if(pos <= mid) Update(x*2,l,mid,pos,val);
        else Update(x*2+1,mid+1,r,pos,val);

        seg[x] = max(seg[x*2],seg[x*2+1]);
    }
}
int Mx(int x, int l, int r, int L, int R) {
    if(l >= L && r <= R) {
        return seg[x];
    }
    else if(l > R || r < L) {
        return 0;
    }
    else {
        int mid = (l+r)/2;
        return max(Mx(x*2,l,mid,L,R),Mx(x*2+1,mid+1,r,L,R));
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int a, b; cin >> a >> b;
        arr[i].fi = a, arr[i].se = b;
        pq.push({i+b,i});
    }
    for(int i = 1; i <= n; i++) {
        int best = Mx(1,1,n,1,i-arr[i].fi-1);

        sol[i] = best+1;
        ans = max(ans,sol[i]);

        while(!pq.empty() && pq.top().fi <= i) {
            pair<int,int> now = pq.top();

            pq.pop();
            Update(1,1,n,now.se,sol[now.se]);
        }
    }
    cout << ans << endl;
    return 0;
}

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