Submission #1211099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211099		simona1230	Radio Towers (IOI22_towers)	C++20	23 / 100	4043 ms	4516 KiB

towers

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


int n,h[100001];
void init(int N, std::vector<int> H)
{
    n=N;
    for(int i=0;i<n;i++)
        h[i]=H[i];
    return;
}

int lf[100001];
int rt[100001];
vector<pair<int,int> > v;
int t[400001];

void upd(int i,int l,int r,int id,int vl)
{
    if(l==r)
    {
        t[i]+=vl;
        return;
    }
    int m=(l+r)/2;
    if(id<=m)upd(i*2,l,m,id,vl);
    else upd(i*2+1,m+1,r,id,vl);

    t[i]=max(t[i*2],t[i*2+1]);
}

int query(int i,int l,int r)
{
    if(l==r)return l;
    int m=(l+r)/2;
    if(t[i*2]!=0)return query(i*2,l,m);
    else return query(i*2+1,m+1,r);
}

int max_towers(int L, int R, int D)
{
    deque<int> a;
    for(int i=0;i<n;i++)
    {
        while(a.size()&&h[a.back()]<h[i])a.pop_back();
        a.push_back(i);

        int id=-1;
        int l=0,r=a.size()-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            if(h[a[m]]>=h[i]+D)
            {
                id=a[m];
                l=m+1;
            }
            else r=m-1;
        }

        lf[i]=id;
    }
    a.clear();

    for(int i=n-1;i>=0;i--)
    {
        while(a.size()&&h[a.back()]<h[i])a.pop_back();
        a.push_back(i);

        int id=n;
        int l=0,r=a.size()-1;
        while(l<=r)
        {
            int m=(l+r)/2;
            if(h[a[m]]>=h[i]+D)
            {
                id=a[m];
                l=m+1;
            }
            else r=m-1;
        }

        rt[i]=id;

    }

    v.clear();
    for(int i=L;i<=R;i++)
    {
        v.push_back({lf[i],rt[i]});
        //cout<<i<<": "<<lf[i]<<" "<<rt[i]<<endl;
        upd(1,0,n,rt[i],1);
    }

    sort(v.begin(),v.end());

    int i=0,ans=0,last=-1;
    while(1)
    {
        while(i<v.size()&&v[i].first<last)
        {
            //cout<<last<<" "<<v[i].first<<endl;
            upd(1,0,n,v[i].second,-1);
            i++;
        }


        //cout<<"! "<<i<<endl;
        if(t[1]==0)break;
        ans++;
        last=query(1,0,n);
        //cout<<v[i].first<<" "<<v[i].second<<" - "<<last<<endl;
    }

    return ans;
}

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