Submission #1065324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065324		Dan4Life	Bouquet (EGOI24_bouquet)	C++17	100 / 100	248 ms	53896 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int mxN = (int)2e5+10;
const int mxLg = 20;

int n, ans;
int L[mxN], R[mxN], dp[mxN];

const int mxSeg = mxN*4*mxLg;
int root[mxN];
int segNodes = 0;
int seg[mxSeg], segL[mxSeg], segR[mxSeg];

int newChild(int p, int v){
    int np = ++segNodes;
    seg[np] = max(seg[p],v);
    return np;
}

int newParent(int lp, int rp){
    int p = ++segNodes;
    seg[p] = max(seg[lp],seg[rp]);
    segL[p] = lp, segR[p] = rp;
    return p;
}

int upd(int p, int i, int v, int l=1, int r=n){
    if(!p or i<l or i>r) return p;
    if(l==r) return newChild(p,v);
    int mid = (l+r)/2;
    if(!segL[p]) segL[p]=++segNodes;
    if(!segR[p]) segR[p]=++segNodes;
    if(i<=mid) return newParent(upd(segL[p],i,v,l,mid),segR[p]);
    return newParent(segL[p],upd(segR[p],i,v,mid+1,r));
}

int query(int p, int i, int l=1, int r=n){
    if(!p or i<l or i>r) return 0;
    int mid = (l+r)/2;
    if(i==r) return seg[p];
    if(i<=mid) return query(segL[p],i,l,mid);
    return max(seg[segL[p]],query(segR[p],i,mid+1,r));
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> L[i] >> R[i];
        L[i]=min(L[i],i-1);
        R[i]=min(R[i],n-i);
    }
    root[0] = ++segNodes; 
    for(int i = 1; i <= n; i++){
        dp[i]=1;
        if(i>1) dp[i]=query(root[i-L[i]-1],i-1)+1;
        ans = max(ans, dp[i]);
        root[i] = upd(root[i-1],i+R[i],dp[i]);
    }
    cout << ans << "\n";
}

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