제출 #1052730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052730		Ludissey	Bouquet (EGOI24_bouquet)	C++17	100 / 100	92 ms	30400 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

vector<int> memo;
int n;



struct node {
    node* left;
    node* right;
    int mx;
    void update(){
        mx=max(left->mx,right->mx);
    }
    node(){
        left=NULL;
        right=NULL;
        mx=0;
    }
};

node ROOT;
void build(node* root, int l, int r){
    if(l==r){
        root->mx=0;
    }else{
        int mid=(l+r)/2;
        root->left=new node();
        root->right=new node();
        build(root->left, l, mid);
        build(root->right, mid+1, r);
        root->update();
    }
}

int query(node* root, int l, int r, int qL, int qR){
    if(l>qR||r<qL) return 0;
    if(l>=qL&&r<=qR){
        return root->mx;
    }
    int mid=(l+r)/2;
    return max(query(root->left, l, mid,qL,qR),query(root->right, mid+1, r,qL,qR));
}

void update(node* root, int l, int r, int p, int v){
    if(l>p||r<p) return;
    if(l==p&&r==p){
        root->mx=v;
        return;
    }
    int mid=(l+r)/2;
    update(root->left, l, mid,p,v);
    update(root->right, mid+1, r,p,v);
    root->update();
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n ;
    memo.resize(n,-1);
    vector<vector<pair<int,int>>> toadd(n);
    vector<int> l,r;
    l.resize(n,-1);
    r.resize(n,-1);
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];
    ROOT.left=NULL;
    ROOT.right=NULL;
    ROOT.mx=0;
    build(&ROOT,0,n-1);
    int ans=0;
    for (int i = n-1; i >= 0; i--)
    {
        for (auto u : toadd[i]) update(&ROOT,0,n-1, u.first, u.second); //first cest le i second cest le mx
        int mx=1;
        if(r[i]+i+1<n) mx=query(&ROOT,0,n-1,r[i]+i+1,n-1)+1;
        if(i-(l[i]+1)>=0) toadd[i-(l[i]+1)].push_back({i,mx});
        ans=max(mx,ans);
    }
    
    cout << ans << "\n";
    return 0;
}

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