oj.uz

Submission #1073643

# Submission time Handle Problem Language Result Execution time Memory
1073643 2024-08-24T16:53:58 Z fv3 Radio Towers (IOI22_towers) C++17
0 / 100
 623 ms 4812 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
const int INF = 1 << 30;

int N;
vector<int> H;

struct node
{
  int mn;
  int index;
};
node merge(const node a, const node b)
{
  return a.mn < b.mn ? a : b;
}
const node empty_node = {INF, 0};

int nt;
vector<int> st_mx;
vector<node> st_mn;

node get_min_range(int l, int r, int k, int tl, int tr)
{
  if (tr < l || tl > r) return empty_node;
  if (tl >= l && tr <= r) return st_mn[k];
  int c = (tl + tr) / 2;
  return merge(get_min_range(l, r, k*2, tl, c), get_min_range(l, r, k*2|1, c+1, tr));
}

void set_min(int i)
{
  i += nt;
  st_mn[i] = empty_node;
  for (i /= 2; i >= 1; i /= 2)
    st_mn[i] = merge(st_mn[i*2], st_mn[i*2|1]);
}

int get_max_range(int l, int r, int k, int tl, int tr)
{
  if (tr < l || tl > r) return 0;
  if (tl >= l && tr <= r) return st_mx[k];
  int c = (l + r) / 2;
  return max(get_max_range(tl, tr, k*2, tl, c), get_max_range(tl, tr, k*2|1, c+1, tr));
}

void init(int N_, vector<int> H_)
{
  N = N_;
  H = H_;

  nt = 1;
  while (nt < N) nt <<= 1;

  st_mx = vector<int>(nt*2);
  st_mn = vector<node>(nt*2, empty_node);

  for (int i = 0; i < N; i++)
  {
    st_mx[nt + i] = H[i];
    st_mn[nt + i] = {H[i], i};
  }

  for (int i = nt - 1; i >= 1; i--)
  {
    st_mx[i] = max(st_mx[i*2], st_mx[i*2|1]);
    st_mn[i] = merge(st_mn[i*2], st_mn[i*2|1]); 
  }
}

int max_towers(int L, int R, int D) 
{
  // You should always lease the smallest tower
  // No two adjacent towers can be leased

  int res = 0;
  set<int> leased;
  while (true)
  {
    node cnd = get_min_range(L, R, 1, 0, nt - 1);
    //cerr << cnd.mn << " " << cnd.index << "\n";
    if (cnd.mn == INF) break;

    if (!leased.size())
    {
      res++;
      leased.insert(cnd.index);
      for (int i = max(L, cnd.index-1); i <= min(R, cnd.index + 1); i++)
        set_min(i);
      continue;
    }

    if (*leased.begin() < cnd.index)
    {
      int l = *--leased.lower_bound(cnd.index);
      int mx = get_max_range(l, cnd.index, 1, 0, nt - 1);
    }
    if (*--leased.end() > cnd.index)
    {
      int r = *leased.lower_bound(cnd.index);
      int mx = get_max_range(cnd.index, r, 1, 0, nt - 1);
    }
 
    res++;
    leased.insert(cnd.index);
    for (int i = max(L, cnd.index-1); i <= min(R, cnd.index + 1); i++)
      set_min(i);
  }

  return res;
}

Compilation message

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:98:11: warning: unused variable 'mx' [-Wunused-variable]
   98 |       int mx = get_max_range(l, cnd.index, 1, 0, nt - 1);
      |           ^~
towers.cpp:103:11: warning: unused variable 'mx' [-Wunused-variable]
  103 |       int mx = get_max_range(cnd.index, r, 1, 0, nt - 1);
      |           ^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 2924 KB 1st lines differ - on the 1st token, expected: '1', found: '10870'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '22'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '22'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 623 ms 4812 KB 1st lines differ - on the 1st token, expected: '11903', found: '15506'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 1880 KB 1st lines differ - on the 1st token, expected: '7197', found: '10306'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '22'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 2924 KB 1st lines differ - on the 1st token, expected: '1', found: '10870'
2 Halted 0 ms 0 KB -