Submission #1212039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212039		simona1230	Radio Towers (IOI22_towers)	C++20	17 / 100	288 ms	4136 KiB

towers

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

const int maxn=1e5+5;

stack<int> s;
int h[maxn];
int t[4*maxn];
int x[maxn];

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

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

int query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[i];
    int m=(l+r)/2;
    return max(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;

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]=0;
        else if(rt[i]==-1)x[i]=query(1,0,n-1,lf[i],i)-h[i];
        else if(lf[i]==-1)x[i]=query(1,0,n-1,i,rt[i])-h[i];
        else x[i]=min(query(1,0,n-1,lf[i],i),query(1,0,n-1,i,rt[i]))-h[i];
        //cout<<i<<" "<<x[i]<<endl;
    }
    //cout<<endl;

    sort(x,x+n);
}

int max_towers(int L, int R, int D)
{
    int ans=n;
    int l=0,r=n-1;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(x[m]>=D)
        {
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    return n-ans+1;
}

/*
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