Submission #1205482

#TimeUsernameProblemLanguageResultExecution timeMemory
1205482moondarksideBouquet (EGOI24_bouquet)C++20
100 / 100
301 ms33020 KiB
#include <iostream>
#include<bits/stdc++.h>
using namespace std;


int getMax(std::vector<int>& SegTree, int L,int R, int n, int target){
    if(R<=target){
        return SegTree[n];
        
        
    }
    if(L>target){
        return -1;
    }
    int a=getMax(SegTree,L,(R+L)/2,n*2,target);
    int b=getMax(SegTree,(L+R)/2+1,R,n*2+1,target);
    return max(a,b);
}

int setPoint(std::vector<int>& SegTree, int L,int R, int n, int target,int val){
    if(R<target){
        return 0;
    }
    SegTree[n]=max(SegTree[n],val);
    if(L>target){
        
        return 0;
    }
    if(L==R){
        return 0;
    }
    setPoint(SegTree,L,(R+L)/2,n*2,target,val);
    setPoint(SegTree,(L+R)/2+1,R,n*2+1,target,val);
    return 0;
}

int main()
{
    int n;
    cin>>n;
    int maxi=1;
    std::vector<int> SegTree(n*4,0);
    map<int,vector<int>> UpdateList;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<UpdateList[i].size();j+=2){
            setPoint(SegTree,0,n,1,UpdateList[i][j],UpdateList[i][j+1]);
        }
        int l,r;
        cin>>l>>r;
        if(i-l-1<0){
            UpdateList[i+r+1].push_back(i);
            UpdateList[i+r+1].push_back(1);
        }
        else{
            UpdateList[i+r+1].push_back(i);
            int v=getMax(SegTree,0,n,1,i-l-1)+1;
            UpdateList[i+r+1].push_back(v);
            maxi=max(v,maxi);
        }
    }
    cout<<maxi;
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...