Submission #1010411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010411		bachhoangxuan	Radio Towers (IOI22_towers)	C++17	100 / 100	1793 ms	46508 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int inf = 1e9;
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second

int N,mn[maxn];
vector<int> H;

namespace ST{
    struct node{
        int mn=inf,mx=-inf;
        int lv=0,rv=0;
        node(){}
        friend node operator+(node a,node b){
            node res;
            res.mn=min(a.mn,b.mn);
            res.mx=max(a.mx,b.mx);
            res.lv=max({a.lv,b.lv,a.mx-b.mn});
            res.rv=max({a.rv,b.rv,b.mx-a.mn});
            return res;
        }
    }tree[4*maxn];
    void build(int l,int r,int id){
        if(l==r){
            tree[id].mn=tree[id].mx=H[l];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    node query(int l,int r,int id,int tl,int tr){
        if(tr<l || r<tl) return node();
        if(tl<=l && r<=tr) return tree[id];
        int mid=(l+r)>>1;
        return query(l,mid,id<<1,tl,tr)+query(mid+1,r,id<<1|1,tl,tr);
    }
}
namespace ST2{
    vector<piii> tree[4*maxn];
    void build(int l,int r,int id){
        for(int i=l;i<=r;i++) tree[id].push_back({mn[i],{i,i}});
        sort(tree[id].begin(),tree[id].end());
        for(int i=(int)tree[id].size()-2;i>=0;i--){
            tree[id][i].se.fi=min(tree[id][i].se.fi,tree[id][i+1].se.fi);
            tree[id][i].se.se=max(tree[id][i].se.se,tree[id][i+1].se.se);
        }
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    }
    piii query(int l,int r,int id,int tl,int tr,int d){
        if(tr<l || r<tl) return {0,{inf,-inf}};
        if(tl<=l && r<=tr){
            int sz=(int)tree[id].size();
            int pos=lower_bound(tree[id].begin(),tree[id].end(),mpp(d,mpp(0,0)))-tree[id].begin();
            if(pos==sz) return {0,{inf,-inf}};
            else return {sz-pos,tree[id][pos].se};
        }
        int mid=(l+r)>>1;
        piii a=query(l,mid,id<<1,tl,tr,d),b=query(mid+1,r,id<<1|1,tl,tr,d);
        return {a.fi+b.fi,{min(a.se.fi,b.se.fi),max(a.se.se,b.se.se)}};
    }
}

void init(int _N, std::vector<int> _H){
    N=_N;H=_H;
    for(int i=0;i<N;i++) mn[i]=inf;
    ST::build(0,N-1,1);
    vector<int> v;
    for(int i=0;i<N;i++){
        while(!v.empty() && H[v.back()]>H[i]) v.pop_back();
        mn[i]=min(mn[i],ST::query(0,N-1,1,(v.empty()?0:v.back()+1),i).mx);
        v.push_back(i);
    }
    v.clear();
    for(int i=N-1;i>=0;i--){
        while(!v.empty() && H[v.back()]>H[i]) v.pop_back();
        mn[i]=min(mn[i],ST::query(0,N-1,1,i,(v.empty()?N-1:v.back()-1)).mx);
        v.push_back(i);
    }
    for(int i=0;i<N;i++){
        mn[i]-=H[i];
        //cout << i << ' ' << mn[i] << '\n';
    }
    ST2::build(0,N-1,1);
}

int max_towers(int L, int R, int D){
    int lt=N,rt=-1;
    int l=L,r=R;
    while(l<=r){
        int mid=(l+r)>>1;
        if(ST::query(0,N-1,1,L,mid).rv>=D) lt=mid,r=mid-1;
        else l=mid+1;
    }
    l=L;r=R;
    while(l<=r){
        int mid=(l+r)>>1;
        if(ST::query(0,N-1,1,mid,R).lv>=D) rt=mid,l=mid+1;
        else r=mid-1;
    }
    //cout << lt << ' ' << rt << '\n';
    auto [cnt,p]=ST2::query(0,N-1,1,L,R,D);
    if(p.fi==inf){
        if(lt<=rt) return 2;
        else return 1;
    }
    if(lt<=p.fi && ST::query(0,N-1,1,lt,p.fi).mx>=H[p.fi]+D) cnt++;
    if(p.se<=rt && ST::query(0,N-1,1,p.se,rt).mx>=H[p.se]+D) cnt++;
    return cnt;
    return 0;
}

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