Submission #1241692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241692		moondarkside	Radio Towers (IOI22_towers)	C++20	0 / 100	199 ms	2452 KiB

towers

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

vector<int> Heights;
vector<int> Join;
vector<int> Carry;


void init(int N, vector<int> H) {
    Heights=H;
}


int max_towers(int L, int R, int D){
    
    if(Join.size()==0){
        
    int am=0;
    int minMax=Heights[L];
    bool cases=false;
    Join.push_back(0);
    std::deque<pair<int,int>>NoSync;
    int baseP=1;
    Carry=vector<int>(Heights.size(),-1);
    Carry[0]=0;
    for(int i=1;i<=Heights.size();i++){
        
        int b=1;
        while(!NoSync.empty() && NoSync.back().first>=Heights[i]){
            b+=NoSync.back().second;
            NoSync.pop_back();
        }
        NoSync.push_back({Heights[i],b});
        
        if(cases){
            
            int b=0;
            while(!NoSync.empty() && NoSync.front().first+D<=Heights[i]){
                    b+=NoSync.front().second;
                    NoSync.pop_front();
            }
            for(int j=baseP;j<baseP+b;j++){
                Carry[j]=i;
            }
            baseP+=b;
            
            
            if(Heights[i]+D<=minMax){
                
                NoSync.clear();
                cases=false;
                am++;
                minMax=Heights[i];
                for(int j=baseP;j<=i;j++){
                    Carry[j]=i;
                }
                baseP=i+1;
                NoSync.clear();
            }
            else{
                minMax=max(minMax,Heights[i]);
            }
            
        }
        else{
            if(Heights[i]-D>=minMax){
                
                cases=true;
                minMax=Heights[i];
            }
            else{
                minMax=min(minMax,Heights[i]);
            }
            
            
            
        }
        
        Join.push_back(am);
        
    } 
        
        
        
        
        
    }
    
    if(Carry[L]==-1){
        return 1;
    }


        
    return max(1,1+Join[R]-Join[Carry[L]]);
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23