Submission #1212096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212096		simona1230	Radio Towers (IOI22_towers)	C++20	17 / 100	473 ms	70836 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;
    node(){}
    node(int mn,int mx,int df)
    {
        minn=mn;
        maxx=mx;
        diff=df;
    }
};

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)};
    r.diff=max(r.diff,n2.maxx-n1.minn);
    return r;
}

void build(int i,int l,int r)
{
    if(l==r)
    {
        t[i]={h[l],h[l],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};
    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 query2(int i,int l,int r,int ql,int qr,int vl)
{
    if(ql>qr)return {(int)1e9,0,0};
    if(ql<=l&&r<=qr)
    {
        int id=-1;
        int ll=0,rr=c[i].size()-1;
        while(ll<=rr)
        {
            int m=(ll+rr)/2;
            if(x[c[i][m]]>=vl)
            {
                id=m;
                ll=m+1;
            }
            else rr=m-1;
        }

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

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

void init(int N, std::vector<int> H)
{
    n=N;
    for(int i=0;i<n;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;
}

int max_towers(int L, int R, int D)
{
    node q=query2(1,0,n-1,L,R,D);
    return q.diff;
}

/*
7 4
10 20 60 40 50 30 70
0 6 10
0 6 20
0 6 30
0 6 40
*/

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