Submission #1233623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233623		coco2311	Bouquet (EGOI24_bouquet)	C++17	100 / 100	66 ms	6848 KiB

Main

#include <iostream>
#include <cmath>
#include <queue>
using namespace std;

#define f first
#define s second

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("input.in","r",stdin);
    int N; cin>>N;
    int dp[N];
    int zp=1<<(int)ceil(log2(N));
    int arb[2*zp];
    pair<int,int> fl[N];
    for(int i=0;i<N;i++){
        cin>>fl[i].f>>fl[i].s;
    }
    for(int i=0;i<2*zp;i++){
        arb[i]=0;
    }
    priority_queue<pair<int,int>> pq; // end flower index
    int id,v,pos;
    int l,r;
    for(int i=0;i<N;i++){
        if(i-fl[i].f<=0){
            dp[i]=1;
        }
        else{
            while(!pq.empty() && (pq.top().f)*-1<i){
                id=pq.top().s;
                v=dp[id];
                pos=id + zp;
                arb[pos]=max(arb[pos],v);
                pos/=2;
                while(pos>=1){
                    arb[pos]=max(arb[pos+pos],arb[pos+pos+1]);
                    pos/=2;
                }
                pq.pop();
            }
            v=0; l=zp; r=zp+i-fl[i].f-1;
            while(l<=r){
                if(l%2==1){
                    v=max(v,arb[l]);
                    l++;
                }
                if(r%2==0){
                    v=max(v,arb[r]);
                    r--;
                }
                r/=2;
                l/=2;
            }
            dp[i]=1+v;
        }
        pq.push({-1*(i+fl[i].s),i});
    }
    int m=0;
    for(int i=0;i<N;i++){
        m=max(m,dp[i]);
    }
    cout<<m;
}

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