Submission #1205463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205463		moondarkside	Bouquet (EGOI24_bouquet)	C++20	8 / 100	260 ms	32860 KiB

Main

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#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(R>target && 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){
        SegTree[n]=max(SegTree[n],val);
        
        return 0;
    }
    if(L<=target){
        setPoint(SegTree,L,(R+L)/2,n*2,target,val);
        setPoint(SegTree,(L+R)/2+1,R,n*2+1,target,val);
        return 0;
    }
    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;
}

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