Submission #1213153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213153		nerrrmin	Radio Towers (IOI22_towers)	C++20	29 / 100	4085 ms	3484 KiB

towers

#include "towers.h"
#define pb push_back
#include <bits/stdc++.h>

const int maxn = 2e5 + 10;
int n;
int a[maxn], t[maxn * 4];
//map < int, int > mp;
int pref[maxn];
void build(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = a[l];
        return;
    }
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    t[i] = std::max(t[2*i], t[2*i+1]);
}

int ql, qr;
int query(int i, int l, int r)
{
    if(qr < l || ql > r)return 0;
    if(ql <= l && r <= qr)return t[i];
    int mid = (l + r)/2;
    return (query(2*i, l, mid), query(2*i+1, mid+1, r));
}
int binomic = 0;
int maxpos,maxmax;
void init(int N, std::vector<int> H)
{
    binomic = 1;
    n = N;
    maxmax = 0;
    for (int i = 0; i < n; ++ i)
    {
        a[i] = H[i];
        maxmax = std::max(maxmax, a[i]);
      //  mp[a[i]] = i;
    }
    for (int i = 0; i < n; ++ i)
    {
        if(a[i] == maxmax)
        {
            maxpos = i;
            break;
        }
        if(a[i] < a[i-1])binomic = 0;
    }
    for (int i = n-1; i >= 0; -- i)
    {
        if(a[i] == maxmax)break;
        if(a[i] < a[i+1])binomic = 0;
    }
    for (int i = 0; i < n; ++ i)
    {
        if(i == 0)
        {
            pref[i] = 0;
            if(a[i] < a[i+1])pref[i] ++;
        }
        else if(i == n-1)
        {
            pref[i] = pref[i-1];
            if(a[i] < a[i-1])pref[i] ++;
        }
        else
        {
            pref[i] = pref[i-1];
            if(a[i] < a[i+1] && a[i] < a[i-1])pref[i] ++;
        }
    }

}


int last[maxn], nxt[maxn];
int active[maxn];
/// shtoto ako imame po malko ot strani ne mojem da go vzemem zaedno s tekushtoto
/// a ako trqbva da izbirame iskame po malkoto
/// taka che vzimame po malkoto??



/***
  abs max
   /\
  /  \
 /    \
/
**/
int max_towers(int L, int R, int D)
{
    if(binomic)
    {
        if(R - L + 1 >= 3 && maxpos > L && maxpos < R)
        {
            if(a[L] + D <= maxmax && a[R] + D <= maxmax)return 2;
            else return 1;
        }
        else return 1;
    }
   if(D == 1)
    {
        int sz = R - L + 1;
        int ans = 0;
        if(L == R)return 1;
        if(sz > 2)
        {
            ans += pref[R-1] - pref[L];
        }
        if(L < n-1 && a[L] < a[L+1])ans ++;
        if(R > 0 && a[R] < a[R-1])ans ++;
        return ans;
    }
    for (int i = L; i <= R; ++ i)
        active[i] = 0;
    std::vector < std::pair < int, int > > g;
    for (int i = L; i <= R; ++ i)
    {
        g.pb(std::make_pair(a[i], i));
    }
    sort(g.begin(), g.end());
    int cnt = 0;
    for (auto &[val, i]: g)
    {
     ///   cout << val << "  " << i << endl;
        int found = 0, no = 0;
        for (int j = i-1; j >= L; -- j)
        {
            if(a[j] >= val + D)
            {
                found = 1;
                break;
            }
            if(active[j])
            {
                no = 1;
                break;
            }
        }
        ///cout << "found1 " << found << endl;
        if(no)continue;
        found = 0;
         for (int j = i+1; j <= R; ++ j)
        {


            if(a[j] >= val + D)
            {
                found = 1;
                break;
            }
            if(active[j])
            {
                no = 1;
                break;
            }
        }
        if(no)continue;
       /// cout <<"found2 " << found << endl;
        active[i] = 1;
        cnt ++;
    }


  return cnt;
}

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