Submission #1212129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212129		simona1230	Radio Towers (IOI22_towers)	C++20	100 / 100	1072 ms	75628 KiB

towers

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

const int maxn=1e5+5;

stack<int> s;

struct node
{
    int minn,maxx,diff,diff2;
    node(){}
    node(int mn,int mx,int df,int df2)
    {
        minn=mn;
        maxx=mx;
        diff=df;
        diff2=df2;
    }
};

int h[maxn];
node t[4*maxn];
int x[maxn];

node pull(node n1,node n2)
{
    node r={min(n1.minn,n2.minn),max(n1.maxx,n2.maxx),max(n1.diff,n2.diff),max(n1.diff2,n2.diff2)};
    r.diff=max(r.diff,n2.maxx-n1.minn);
    r.diff2=max(r.diff2,n1.maxx-n2.minn);
    return r;
}

void build(int i,int l,int r)
{
    if(l==r)
    {
        t[i]={h[l],h[l],0,0};
        return;
    }

    int m=(l+r)/2;
    build(i*2,l,m);
    build(i*2+1,m+1,r);
    t[i]=pull(t[i*2],t[i*2+1]);
}

node query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return {(int)1e9,0,0,0};
    if(ql<=l&&r<=qr)return t[i];
    int m=(l+r)/2;
    return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(ql,m+1),qr));
}

int lf[maxn];
int rt[maxn];
int n;

vector<int> c[4*maxn],minn[4*maxn],maxx[4*maxn];

bool cmp(int i,int j)
{
    return x[i]>x[j];
}

void build2(int i,int l,int r)
{
    if(l==r)
    {
        c[i].push_back(l);
        minn[i].push_back(l);
        maxx[i].push_back(l);
        return;
    }
    int m=(l+r)/2;
    build2(i*2,l,m);
    build2(i*2+1,m+1,r);
    //cout<<i<<" "<<l<<" "<<r<<endl;

    c[i]=c[i*2+1];
    for(int j=0;j<c[i*2].size();j++)
        c[i].push_back(c[i*2][j]);
    sort(c[i].begin(),c[i].end(),cmp);
    minn[i]=maxx[i]=c[i];
    minn[i][0]=maxx[i][0]=c[i][0];
    for(int j=1;j<c[i].size();j++)
        minn[i][j]=min(c[i][j],minn[i][j-1]),
        maxx[i][j]=max(c[i][j],maxx[i][j-1]);
}

node qq[4*maxn];
int ll,rr,md,id;
node query2(int i,int l,int r,int ql,int qr,int vl)
{
    if(ql>qr)return {(int)1e9,0,0,0};
    if(ql<=l&&r<=qr)
    {
        id=-1;
        ll=0,rr=c[i].size()-1;
        while(ll<=rr)
        {
            int md=(ll+rr)/2;
            if(x[c[i][md]]>=vl)
            {
                id=md;
                ll=md+1;
            }
            else rr=md-1;
        }

        if(id==-1)return {(int)1e9,0,0,0};
        else return {minn[i][id],maxx[i][id],id+1,0};
    }

    int m=(l+r)/2;
    qq[i*2]=query2(i*2,l,m,ql,min(qr,m),vl);
    qq[i*2+1]=query2(i*2+1,m+1,r,max(m+1,ql),qr,vl);
    return {min(qq[i*2].minn,qq[i*2+1].minn),max(qq[i*2].maxx,qq[i*2+1].maxx),qq[i*2].diff+qq[i*2+1].diff,0};
}

int one;

void init(int N, std::vector<int> H)
{
    n=N;
    for(int i=0;i<n;i++)
    {
        if(i==0||H[i]>H[i-1])one=i;
        h[i]=H[i];

        while(s.size()&&h[s.top()]>h[i])s.pop();
        if(s.size())lf[i]=s.top();
        else lf[i]=-1;
        s.push(i);
    }

    while(s.size())s.pop();
    build(1,0,n-1);

    for(int i=n-1;i>=0;i--)
    {
        while(s.size()&&h[s.top()]>h[i])s.pop();
        if(s.size())rt[i]=s.top();
        else rt[i]=-1;
        s.push(i);

        if(lf[i]==-1&&rt[i]==-1)x[i]=1e9;
        else if(rt[i]==-1)x[i]=query(1,0,n-1,lf[i],i).maxx-h[i];
        else if(lf[i]==-1)x[i]=query(1,0,n-1,i,rt[i]).maxx-h[i];
        else x[i]=min(query(1,0,n-1,lf[i],i).maxx,query(1,0,n-1,i,rt[i]).maxx)-h[i];
        //cout<<i<<" "<<x[i]<<endl;
    }

    build2(1,0,n-1);
    //cout<<endl;
}

node q;
int l,r,m,id1,id2;
int max_towers(int L, int R, int D)
{
    q=query2(1,0,n-1,L,R,D);
    if(q.minn==1e9)
    {
        id=-1;
        l=L,r=R;
        while(l<=r)
        {
            m=(l+r)/2;
            if(query(1,0,n-1,L,m).diff>=D)
            {
                id=m;
                r=m-1;
            }
            else l=m+1;
        }

        if(id!=-1&&query(1,0,n-1,id,R).diff2>=D)return 2;
        return 1;
    }
    //cout<<q.minn<<" "<<q.maxx<<endl;
    l=L,r=q.minn;
    id1=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        if(query(1,0,n-1,m,q.minn).maxx>=h[q.minn]+D)
        {
            id1=m;
            l=m+1;
        }
        else r=m-1;
    }

    l=q.maxx,r=R;
    id2=-1;
    while(l<=r)
    {
        m=(l+r)/2;
        //cout<<m<<" "<<R<<" - "<<query(1,0,n-1,m,R).maxx<<endl;
        if(query(1,0,n-1,q.maxx,m).maxx>=h[q.maxx]+D)
        {
            id2=m;
            r=m-1;
        }
        else l=m+1;
    }

    //cout<<id1<<" "<<id2<<endl;

    if(id1!=-1&&query(1,0,n-1,L,id1).diff>=D)q.diff++;
    if(id2!=-1&&query(1,0,n-1,id2,R).diff2>=D)q.diff++;

    return q.diff;
}

/*
7 4
10 20 60 40 50 30 70
1 2 10
1 6 20
3 6 30
2 4 40
*/

• 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