Submission #1014767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014767		kunzaZa183	Radio Towers (IOI22_towers)	C++17	23 / 100	4035 ms	9556 KiB

towers

#include "towers.h"

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

const int maxn = 100000;

vector<int> val, all;
int numval;

struct segtree {
  int seg[4 * maxn];

  void update(int curin, int curl, int curr, int in, int val) {
    if (in < curl || in > curr) return;
    if (curl == curr) {
      seg[curin] = max(seg[curin], val);
      return;
    }
    update(curin * 2 + 1, curl, (curl + curr) / 2, in, val),
        update(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
    seg[curin] = max(seg[curin * 2 + 1], seg[curin * 2 + 2]);
  }

  int query(int curin, int curl, int curr, int ql, int qr) {
    if (ql > curr || qr < curl) return 0;
    if (ql <= curl && curr <= qr) return seg[curin];
    return max(query(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
               query(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
  }
} up, down;

void init(int N, vector<int> H) {
  all = H;
  set<int> si;
  for (int i = 0; i < N; i++) si.insert(H[i]);
  numval = si.size();
  for (auto a : si) val.push_back(a);
  // for (auto a : val) cout << a << ' ';
  // cout << "\n";
}

int max_towers(int L, int R, int D) {
  memset(up.seg, 0, sizeof up.seg);
  memset(down.seg, 0, sizeof down.seg);
  for (int i = L; i <= R; i++) {
    int small =
        upper_bound(val.begin(), val.end(), all[i] - D) - val.begin() - 1;
    int exact = lower_bound(val.begin(), val.end(), all[i]) - val.begin();
    int higher = lower_bound(val.begin(), val.end(), all[i] + D) - val.begin();
    // cout << i << ' ' << L << ' ' << R << " ";
    // cout << small << " " << exact << " " << higher << "\n";
    if (small >= 0)
      down.update(0, 0, numval - 1, exact,
                  up.query(0, 0, numval - 1, 0, small));
    if (higher >= 0)
      up.update(0, 0, numval - 1, exact,
                down.query(0, 0, numval - 1, higher, numval - 1) + 1);
    // cout << "UP: ";
    // for (int i = 0; i < numval; i++)
    //   cout << up.query(0, 0, numval - 1, i, i) << " ";
    // cout << "\nDOWN: ";
    // for (int i = 0; i < numval; i++)
    //   cout << down.query(0, 0, numval - 1, i, i) << " ";
    // cout << "\n";
  }
  return up.query(0, 0, numval - 1, 0, numval - 1);
}

• 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