Submission #1023128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023128		JakobZorz	Radio Towers (IOI22_towers)	C++17	100 / 100	1157 ms	105416 KiB

towers

#include"towers.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

const int TREE_SIZE=1<<17;

int n;
vector<int>arr;
vector<int>thres;
vector<int>prv,nxt;
vector<vector<int>>arr_rmq;
vector<vector<pair<int,int>>>arr_rmq2;
vector<vector<int>>thres_rmq;

void init_prev(){
    prv.resize(n);
    vector<int>s;
    for(int i=0;i<n;i++){
        while(s.size()&&arr[s.back()]>arr[i])
            s.pop_back();
        if(s.empty())
            prv[i]=-1;
        else
            prv[i]=s.back();
        s.push_back(i);
    }
}

void init_nxt(){
    nxt.resize(n);
    vector<int>s;
    for(int i=n-1;i>=0;i--){
        while(s.size()&&arr[s.back()]>arr[i])
            s.pop_back();
        if(s.empty())
            nxt[i]=-1;
        else
            nxt[i]=s.back();
        s.push_back(i);
    }
}

void init_arr_rmq(){
    arr_rmq=vector<vector<int>>(20,vector<int>(n));
    arr_rmq[0]=arr;
    for(int p=1;p<20;p++){
        for(int i=0;i+(1<<p)<=n;i++){
            arr_rmq[p][i]=max(arr_rmq[p-1][i],arr_rmq[p-1][i+(1<<(p-1))]);
        }
    }
}

int get_arr_max(int l,int r){
    int pw2=2;
    int p=0;
    while(pw2<r-l){
        pw2*=2;
        p++;
    }
    pw2/=2;
    return max(arr_rmq[p][l],arr_rmq[p][r-pw2]);
}

void init_thres(){
    thres.resize(n);
    for(int i=0;i<n;i++){
        int mn=2e9;
        
        if(prv[i]!=-1){
            int mx1=get_arr_max(prv[i],i);
            mn=min(mn,mx1);
        }
        
        if(nxt[i]!=-1){
            int mx2=get_arr_max(i,nxt[i]);
            mn=min(mn,mx2);
        }
        
        thres[i]=mn-arr[i];
    }
}

void init_thres_rmq(){
    thres_rmq=vector<vector<int>>(20,vector<int>(n));
    thres_rmq[0]=thres;
    for(int p=1;p<20;p++){
        for(int i=0;i+(1<<p)<=n;i++){
            thres_rmq[p][i]=max(thres_rmq[p-1][i],thres_rmq[p-1][i+(1<<(p-1))]);
        }
    }
}

int get_thres_max(int l,int r){
    int pw2=2;
    int p=0;
    while(pw2<r-l){
        pw2*=2;
        p++;
    }
    pw2/=2;
    return max(thres_rmq[p][l],thres_rmq[p][r-pw2]);
}

void init_arr_rmq2(){
    arr_rmq2=vector<vector<pair<int,int>>>(20,vector<pair<int,int>>(n));
    for(int i=0;i<n;i++)
        arr_rmq2[0][i]={arr[i],i};
    for(int p=1;p<20;p++){
        for(int i=0;i+(1<<p)<=n;i++){
            arr_rmq2[p][i]=min(arr_rmq2[p-1][i],arr_rmq2[p-1][i+(1<<(p-1))]);
        }
    }
}

pair<int,int>get_arr_min(int l,int r){
    int pw2=2;
    int p=0;
    while(pw2<r-l){
        pw2*=2;
        p++;
    }
    pw2/=2;
    return min(arr_rmq2[p][l],arr_rmq2[p][r-pw2]);
}

struct Diff{
    vector<int>mn;
    vector<int>mx;
    vector<int>tree;
    Diff():tree(2*TREE_SIZE),mn(2*TREE_SIZE),mx(2*TREE_SIZE){}
    
    void update(int i,int x){
        i+=TREE_SIZE;
        mn[i]=x;
        mx[i]=x;
        tree[i]=0;
        i/=2;
        while(i){
            mn[i]=min(mn[2*i],mn[2*i+1]);
            mx[i]=max(mx[2*i],mx[2*i+1]);
            tree[i]=max(max(tree[2*i],tree[2*i+1]),mx[2*i]-mn[2*i+1]);
            i/=2;
        }
    }
    
    pair<pair<int,int>,int>get(int node,int rl,int rr,int l,int r){
        if(r<=rl||rr<=l)
            return{{(int)1e9+1,-1},0};
        if(l<=rl&&rr<=r)
            return{{mn[node],mx[node]},tree[node]};
        int mid=(rl+rr)/2;
        auto res1=get(2*node,rl,mid,l,r);
        auto res2=get(2*node+1,mid,rr,l,r);
        int mn1=res1.first.first;
        int mx1=res1.first.second;
        int r1=res1.second;
        int mn2=res2.first.first;
        int mx2=res2.first.second;
        int r2=res2.second;
        int mn=min(mn1,mn2);
        int mx=max(mx1,mx2);
        int rs=max(max(r1,r2),mx1-mn2);
        return{{mn,mx},rs};
    }
    
    int get(int l,int r){
        return get(1,0,TREE_SIZE,l,r).second;
    }
};

Diff diff1,diff2;

struct Node{
    int sum;
    Node*ch1,*ch2;
    Node():sum(0),ch1(nullptr),ch2(nullptr){}
};

int get(Node*node,int rl,int rr,int l,int r){
    if(node==nullptr)
        return 0;
    if(r<=rl||rr<=l)
        return 0;
    if(l<=rl&&rr<=r)
        return node->sum;
    int mid=(rl+rr)/2;
    return get(node->ch1,rl,mid,l,r)+get(node->ch2,mid,rr,l,r);
}

int get_sum(Node*node){
    if(node==nullptr)
        return 0;
    return node->sum;
}

Node*update(Node*node,int rl,int rr,int i){
    if(rl==rr-1){
        node=new Node;
        node->sum=1;
        return node;
    }
    int mid=(rl+rr)/2;
    Node*new_node=new Node;
    new_node->ch1=node->ch1;
    new_node->ch2=node->ch2;
    new_node->ch1=node->ch1;
    if(i>=mid){
        if(!node->ch2)
            node->ch2=new Node;
        new_node->ch2=update(node->ch2,mid,rr,i);
    }else{
        if(!node->ch1)
            node->ch1=new Node;
        new_node->ch1=update(node->ch1,rl,mid,i);
    }
    new_node->sum=get_sum(new_node->ch1)+get_sum(new_node->ch2);
    return new_node;
}

vector<pair<int,Node*>>trees;

void init_tree(){
    vector<pair<int,int>>vec(n);
    for(int i=0;i<n;i++)
        vec[i]={thres[i],i};
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    
    trees.resize(n+1);
    Node*root=new Node;
    trees[0]={(int)1e9+1,root};
    for(int i=0;i<n;i++){
        root=update(root,0,TREE_SIZE,vec[i].second);
        trees[i+1].first=vec[i].first;
        trees[i+1].second=root;
    }
}

void init(int N,vector<int>H){
    arr=H;
    n=(int)arr.size();
    init_prev();
    init_nxt();
    init_arr_rmq();
    init_thres();
    init_thres_rmq();
    init_arr_rmq2();
    for(int i=0;i<n;i++){
        diff1.update(i,arr[i]);
        diff2.update(i,arr[n-i-1]);
    }
    init_tree();
}

int max_towers(int L,int R,int D){
    int res=0;
    /*for(int i=L;i<=R;i++){
        if(thres[i]>=D){
            res++;
        }
    }*/
    {
        int l=0,r=n+2;
        while(l<r-1){
            int mid=(l+r)/2;
            if(trees[mid].first>=D)
                l=mid;
            else
                r=mid;
        }
        res+=get(trees[l].second,0,TREE_SIZE,L,R+1);
    }
    
    int first=-1,last=-1;
    if(get_thres_max(L,R+1)<D){
        first=get_arr_min(L,R+1).second;
        last=first;
        res=1;
    }else{
        {
            int l=L,r=R+1;
            while(l<r-1){
                int mid=(l+r)/2;
                if(get_thres_max(L,mid)>=D)
                    r=mid;
                else
                    l=mid;
            }
            first=l;
        }
        
        {
            int l=L,r=R+1;
            while(l<r-1){
                int mid=(l+r)/2;
                if(get_thres_max(mid,R+1)>=D)
                    l=mid;
                else
                    r=mid;
            }
            last=l;
        }
    }
    
    if(get_arr_max(L,first)>=arr[first]+D){
        int l=L,r=first;
        while(l<r-1){
            int mid=(l+r)/2;
            if(get_arr_max(mid,first)>=arr[first]+D)
                l=mid;
            else
                r=mid;
        }
        res+=diff2.get(n-l-1,n-L)>=D;
    }
    
    if(get_arr_max(last,R+1)>=arr[last]+D){
        int l=last,r=R+1;
        while(l<r-1){
            int mid=(l+r)/2;
            if(get_arr_max(last,mid)>=arr[last]+D)
                r=mid;
            else
                l=mid;
        }
        res+=diff1.get(l,R+1)>=D;
    }
    
    return res;
}

Compilation message (stderr)

towers.cpp: In constructor 'Diff::Diff()':
towers.cpp:131:16: warning: 'Diff::tree' will be initialized after [-Wreorder]
  131 |     vector<int>tree;
      |                ^~~~
towers.cpp:129:16: warning:   'std::vector<int> Diff::mn' [-Wreorder]
  129 |     vector<int>mn;
      |                ^~
towers.cpp:132:5: warning:   when initialized here [-Wreorder]
  132 |     Diff():tree(2*TREE_SIZE),mn(2*TREE_SIZE),mx(2*TREE_SIZE){}
      |     ^~~~

• 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