Submission #735348

#	Time	Username	Problem	Language	Result	Execution time	Memory
735348		math_rabbit_1028	Radio Towers (IOI22_towers)	C++17	23 / 100	4086 ms	5788 KiB

towers

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

int n;
vector<int> arr;
int sort_index[101010];


struct maxseg {
  int tree[404040];
  vector<int> initarr;
  void init(int v, int st, int ed) {
    if (st == ed) {
      tree[v] = initarr[st];
      return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid);
    init(2 * v + 1, mid + 1, ed);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  }
  void update(int v, int st, int ed, int idx, int val) {
    if (idx < st || idx > ed) return;
    if (idx == st && idx == ed) {
      tree[v] = val;
      return;
    }
    int mid = (st + ed) / 2;
    update(2 * v, st, mid, idx, val);
    update(2 * v + 1, mid + 1, ed, idx, val);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  }
  int get(int v, int st, int ed, int gs, int ge) {
    if (st > ge || ed < gs) return -1;
    if (gs <= st && ed <= ge) return tree[v];
    int mid = (st + ed) / 2;
    return max(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
  }
} max_value, left_index;

struct minseg {
  int tree[404040];
  vector<int> initarr;
  void init(int v, int st, int ed) {
    if (st == ed) {
      tree[v] = initarr[st];
      return;
    }
    int mid = (st + ed) / 2;
    init(2 * v, st, mid);
    init(2 * v + 1, mid + 1, ed);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  }
  void update(int v, int st, int ed, int idx, int val) {
    if (idx < st || idx > ed) return;
    if (idx == st && idx == ed) {
      tree[v] = val;
      return;
    }
    int mid = (st + ed) / 2;
    update(2 * v, st, mid, idx, val);
    update(2 * v + 1, mid + 1, ed, idx, val);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  }
  int get(int v, int st, int ed, int gs, int ge) {
    if (st > ge || ed < gs) return n;
    if (gs <= st && ed <= ge) return tree[v];
    int mid = (st + ed) / 2;
    return min(get(2 * v, st, mid, gs, ge), get(2 * v + 1, mid + 1, ed, gs, ge));
  }
} right_index;

void init(int N, vector<int> H) {
  n = N;
  vector< pair<int, int> > temp;
  for (int i = 0; i < N; i++) arr.push_back(H[i]);
  for (int i = 0; i < N; i++) temp.push_back({H[i], i});
  sort(temp.begin(), temp.end());
  for (int i = 0; i < N; i++) {
    sort_index[i] = temp[i].second;
  }
  max_value.initarr = arr;
  right_index.initarr = vector<int>(n, n);
  left_index.initarr = vector<int>(n, -1);
  max_value.init(1, 0, n - 1);
}


int max_towers(int L, int R, int D) {
  int ans = 0;
  left_index.init(1, 0, n - 1);
  right_index.init(1, 0, n - 1);

  for (int i = 0; i < n; i++) {
    if (sort_index[i] < L || sort_index[i] > R) continue;
    bool f = true;

    int j = right_index.get(1, 0, n - 1, sort_index[i] + 1, R);
    //cout << sort_index[i] << " " << j << "\n";
    if (j >= 0 && j < n)
      if (max_value.get(1, 0, n - 1, sort_index[i] + 1, j - 1) < max(arr[sort_index[i]], arr[j]) + D) 
        f = false;
    j = left_index.get(1, 0, n - 1, L, sort_index[i] - 1);
    //cout << j << " " << sort_index[i] << "\n";  
    if (j >= 0 && j < n)
      if (max_value.get(1, 0, n - 1, j + 1, sort_index[i] - 1) < max(arr[sort_index[i]], arr[j]) + D) 
        f = false;

    if (f) {
      ans++;
      left_index.update(1, 0, n - 1, sort_index[i], sort_index[i]);
      right_index.update(1, 0, n - 1, sort_index[i], sort_index[i]);
    }
  }
  return ans;
}

• 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