Submission #1055628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055628		vjudge1	Radio Towers (IOI22_towers)	C++17	23 / 100	4067 ms	94048 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;
vector<int>H,addto;
void init(int N, std::vector<int> H_) {
    H=H_;
}
struct fenwickt{
    int T[100100];
    int qry(int n){
        n++;
        int ans=0;
        while(n)
            ans=max(ans,T[n]),n-=n&-n;
        return ans;
    }
    void upd(int n,int p){
        n++;
        while(n<100100)
            T[n]=max(T[n],p),n+=n&-n;
    }
} ST;

vector<pair<int,int>>inser[100100];
int max_towers(int l, int r, int D) {
    int n=H.size();
    vector<int>stk;
    stk.push_back(n);
    H.push_back(2e9);
    addto.resize(n);
    for(int i=r;i>=l;i--){
        while(H[stk.back()]<H[i])
            stk.pop_back();
        H[i]+=D;
        addto[i]=*--upper_bound(stk.begin(),stk.end(),i,[](int a,int b){
            return H[a]>H[b];
        });
        H[i]-=D;
        stk.push_back(i);
    }
    int ans=0;
    stk.clear();
    for(int i=l;i<=r;i++){
        for(auto[pos,v]:inser[i])
            ST.upd(pos,v);
        while(stk.size()&&H[stk.back()]<H[i])
            stk.pop_back();
        H[i]+=D;
        auto it=upper_bound(stk.begin(),stk.end(),i,[](int a,int b){
            return H[a]>H[b];
        });
        H[i]-=D;
        int Pos=0;
        if(it!=stk.begin())
        Pos=*--it;
        int dp=ST.qry(Pos-1)+1;
        inser[addto[i]+1].push_back({i,dp});
        ans=max(ans,dp);
        stk.push_back(i);
    }

    return ans;
}

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