Submission #1077593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077593		Hanksburger	Radio Towers (IOI22_towers)	C++17	17 / 100	877 ms	30920 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int seg[400005], order[100005], a[100005], n;
vector<int> h, seglist[400005];
set<int> s;
bool cmp(int x, int y)
{
  return h[x]<h[y];
}
void build(int i, int l, int r)
{
  if (l==r)
  {
    if (l==-1 || l==n)
      seg[i]=2e9;
    else
      seg[i]=h[l];
    return;
  }
  int m=(l+r+2)/2-1;
  build(i*2, l, m);
  build(i*2+1, m+1, r);
  seg[i]=max(seg[i*2], seg[i*2+1]);
}
int query(int i, int l, int r, int ql, int qr)
{
  if (ql<=l && r<=qr)
    return seg[i];
  int m=(l+r+2)/2-1, res=0;
  if (ql<=m && l<=qr)
    res=max(res, query(i*2, l, m, ql, qr));
  if (ql<=r && m<qr)
    res=max(res, query(i*2+1, m+1, r, ql, qr));
  return res;
}
void buildlist(int i, int l, int r)
{
  if (l==r)
  {
    seglist[i].push_back(a[l]);
    //cout << i << ' ' << a[l] << '\n';
    return;
  }
  int m=(l+r)/2;
  buildlist(i*2, l, m);
  buildlist(i*2+1, m+1, r);
  for (int x:seglist[i*2])
    seglist[i].push_back(x);
  for (int x:seglist[i*2+1])
    seglist[i].push_back(x);
  sort(seglist[i].begin(), seglist[i].end());
}
int querylist(int i, int l, int r, int ql, int qr, int x)
{
  if (ql<=l && r<=qr)
  {
    int ind=lower_bound(seglist[i].begin(), seglist[i].end(), x)-seglist[i].begin();
    //cout << l << ' ' << r << ": ";
    //for (int x:seglist[i])
    //    cout << x << ' ';
    //cout << "    " << ind << '\n';
    return seglist[i].size()-ind;
  }
  int m=(l+r)/2, res=0;
  if (ql<=m && l<=qr)
    res+=querylist(i*2, l, m, ql, qr, x);
  if (ql<=r && m<qr)
    res+=querylist(i*2+1, m+1, r, ql, qr, x);
  return res;
}
void init(int N, vector<int> H)
{
  n=N;
  h=H;
  build(1, -1, n);
  for (int i=0; i<n; i++)
    order[i]=i;
  sort(order, order+n, cmp);
  s.insert(-2);
  s.insert(n+1);
  for (int i=0; i<n; i++)
  {
    int ind=order[i];
    auto it=s.lower_bound(ind);
    int l=*prev(it), r=*it;
    int res1=(ind-l==1?0:query(1, -1, n, l+1, ind-1));
    int res2=(r-ind==1?0:query(1, -1, n, ind+1, r-1));
    a[ind]=min(res1, res2)-h[ind];
    s.insert(ind);
  }
  buildlist(1, 0, n-1);
}
int max_towers(int l, int r, int d)
{
  return querylist(1, 0, n-1, l, r, d);
}

• 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