Submission #1227131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227131		LeonidCuk	Radio Towers (IOI22_towers)	C++20	23 / 100	4046 ms	16728 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
vector<int>v,stmax,stmin;
map<int,int>m;
int n;
void build(int i,int l,int r)
{
    if(l==r)
    {
        stmax[i]=v[l];
        stmin[i]=v[l];
        return;
    }
    int m=(l+r)/2;
    build(2*i,l,m);
    build(2*i+1,m+1,r);
    stmax[i]=max(stmax[2*i],stmax[2*i+1]);
    stmin[i]=min(stmin[2*i],stmin[2*i+1]);
}
int gmax(int i,int l,int r,int tl,int tr)
{
    if(l>r||tl>r||l>tr)return 0;
    if(tl<=l&&r<=tr)return stmax[i];
    int m=(l+r)/2;
    return max(gmax(2*i,l,m,tl,tr),gmax(2*i+1,m+1,r,tl,tr));
}
int gmin(int i,int l,int r,int tl,int tr)
{
    if(l>r||tl>r||l>tr)return 1e9;
    if(tl<=l&&r<=tr)return stmin[i];
    int m=(l+r)/2;
    return min(gmin(2*i,l,m,tl,tr),gmin(2*i+1,m+1,r,tl,tr));
}
void init(int N, vector<int>H)
{
    n=N;
    stmax.resize(4*n+1);
    stmin.resize(4*n+1);
    v.resize(n);
    for(int i=0;i<n;i++)
    {

        v[i]=H[i];
        m[v[i]]=i;
    }
    build(1,0,n-1);
}
int dvq(int l,int r,int k,int d)
{
    if(r<l)return 0;
    if(r==l)
    {
        if(v[l]<=k)return 1;
        else return 0;
    }
    int tmin=gmin(1,0,n-1,l,r),tmax=gmax(1,0,n-1,l,r),t=m[tmax];
    if(tmin>k)return 0;
    else return max(1,dvq(l,t-1,tmax-d,d)+dvq(t+1,r,tmax-d,d));
}
int max_towers(int l,int r,int d)
{
    return dvq(l,r,2e9,d);
}

• 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