oj.uz

Submission #970654

# Submission time Handle Problem Language Result Execution time Memory
970654 2024-04-27T03:03:04 Z nguyentunglam Radio Towers (IOI22_towers) C++17
11 / 100
 262 ms 410700 KB 
#include "towers.h"
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1e5 + 10, S = 5e6;

int h[N], lg[N], mx[20][N], mn[20][N], L[N], R[N];

int n;

vector<int> rrh, pos[N];

int idx(int x) {
  return upper_bound(all(rrh), x) - rrh.begin();
}

struct ITSUM {
struct node {
  int left, right, val;
  node () {
    left = right = val = 0;
  }
} T[S];

int cnt;
int it[N];

void pass (int x, int y) {
  T[it[x] = ++cnt] = T[it[y]];
}

void up(int s, int l, int r, int pos, int val) {
  if (l == r) {
    T[s].val += val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) {
    T[++cnt] = T[T[s].left];
    T[s].left = cnt;
    up(T[s].left, l, mid, pos, val);
  }
  else {
    T[++cnt] = T[T[s].right];
    T[s].right = cnt;
    up(T[s].right, mid + 1, r, pos, val);
  }
  T[s].val = T[T[s].left].val + T[T[s].right].val;
}

int get(int s, int l, int r, int from, int to) {
  if (l > to || r < from || s == 0) return 0;
  if (from <= l && r <= to) return T[s].val;
  int mid = l + r >> 1;
  return get(T[s].left, l, mid, from, to) + get(T[s].right, mid + 1, r, from, to);
}
} itsum;

struct ITMAX {
struct node {
  int left, right, val;
  node () {
    left = right = 0;
    val = -1e9;
  }
} T[S];

int cnt;
int it[N];

void pass (int x, int y) {
  T[it[x] = ++cnt] = T[it[y]];
}

void up(int s, int l, int r, int from , int to, int val) {
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    T[s].val = max(T[s].val, val);
    return;
  }
  int mid = l + r >> 1;
  T[++cnt] = T[T[s].left];
  T[s].left = cnt;
  T[++cnt] = T[T[s].right];
  T[s].right = cnt;
  up(T[s].left, l, mid, from, to, val);
  up(T[s].right, mid + 1, r, from, to, val);
}

int get(int s, int l, int r, int pos) {
//  cerr << s << " " << l << " " << r << endl;
  if (l == r || !s) return T[s].val;
  int mid = l + r >> 1;
//  cout << T[s].left << e
//  exit(0);
  if (pos <= mid) return max(T[s].val, get(T[s].left, l, mid, pos));
  return max(T[s].val, get(T[s].right, mid + 1, r, pos));
}
} itmax0, itmax1;

int getmax(int l, int r) {
  if (l > r) return -1e9;
  int k = lg[r - l + 1];
  return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}

int best (int x, int y) {
  return h[x] < h[y] ? x : y;
}

int getmin(int l, int r) {
  if (l > r) return -1e9;
  int k = lg[r - l + 1];
  return best(mn[k][l], mn[k][r - (1 << k) + 1]);
}

priority_queue<int> Q[N];

bool alive[N];

void init(int N, std::vector<int> H) {
  n = N;
  for(int i = 0; i < n; i++) h[i] = H[i];
  stack<int> st;
  for(int i = 0; i < n; i++) {
    while (!st.empty() && h[st.top()] >= h[i]) st.pop();
    L[i] = st.empty() ? -1 : st.top();
    st.push(i);
  }
  while (!st.empty()) st.pop();
  for(int i = n - 1; i >= 0; i--) {
    while (!st.empty() && h[st.top()] >= h[i]) st.pop();
    R[i] = st.empty() ? n : st.top();
    st.push(i);
  }

  for(int i = 0; i < n; i++) mx[0][i] = h[i], mn[0][i] = i;
  for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
  for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 < n; i++) {
    mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << j - 1)]);
    mn[j][i] = best(mn[j - 1][i], mn[j - 1][i + (1 << j - 1)]);
  }

  for(int i = 0; i < n; i++) {
    int tmp = min(getmax(L[i] + 1, i - 1), getmax(i + 1, R[i] - 1)) - h[i];
    rrh.push_back(getmax(L[i] + 1, i - 1) - h[i]);
    rrh.push_back(getmax(i + 1, R[i] - 1) - h[i]);
  }

  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());

  int m = rrh.size();

  for(int i = 0; i < n; i++) {
    int tmp = min(getmax(L[i] + 1, i - 1), getmax(i + 1, R[i] - 1)) - h[i];
//    cout << getmax(L[i] + 1, i - 1) << " " << getmax(i + 1, R[i] - 1) << " " << i << endl;
    pos[idx(tmp)].push_back(i);
  }

  for(int val = m; val >= 1; val--) {
    itsum.pass(val, val + 1);
    for(int &i : pos[val]) {
      itsum.up(itsum.it[val], 0, n - 1, i, 1);
    } pos[val].clear();
  }

  for(int i = 0; i < n; i++) {
    int tmp = getmax(i + 1, R[i] - 1) - h[i];
//    cout << idx(tmp) << endl;
    pos[idx(tmp)].push_back(i);
  }

  for(int val = m; val >= 1; val--) {
    itmax0.pass(val, val + 1);
    for(int &i : pos[val]) {
      itmax0.up(itmax0.it[val], 0, n - 1, L[i] + 1, i, -i);
//      cout << itmax0.get(itmax0.it[val], 0, n - 1, i) << endl;
    } pos[val].clear();
  }

  for(int i = 0; i < n; i++) {
    int tmp = getmax(L[i] + 1, i - 1) - h[i];
    pos[idx(tmp)].push_back(i);
  }

  for(int val = m; val >= 1; val--) {
    itmax1.pass(val, val + 1);
    for(int &i : pos[val]) {
      itmax1.up(itmax1.it[val], 0, n - 1, i, R[i] - 1, i);
    }
  }
}

int max_towers(int l, int r, int d) {
  int tmp = idx(d - 1) + 1;

  int ans = itsum.get(itsum.it[tmp], 0, n - 1, l, r);

//  cout << ans << endl;
  int left = -itmax0.get(itmax0.it[tmp], 0, n - 1, l);
  int right = itmax1.get(itmax1.it[tmp], 0, n - 1, r);


  int smallest = getmin(l, r);
//  cout << smallest << " " << left << " " << right << endl;

  if (left >= l && left <= r && left != smallest && getmax(L[left] + 1, left - 1) - d < h[left]) {
    ans++;
  }
//  exit(0);

  if (right >= l && right <= r && right != smallest && getmax(right + 1, R[right] - 1) - d < h[right]) {
    ans++;
  }

  if (getmax(L[smallest] + 1, smallest - 1) - d < h[smallest] || getmax(smallest + 1, R[smallest] - 1) - d < h[smallest]) ans++;

  return ans;
}

#ifdef ngu
int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int L, R, D;
    assert(3 == scanf("%d %d %d", &L, &R, &D));
    printf("%d\n", max_towers(L, R, D));
  }
  return 0;
}
#endif // ngu

Compilation message

towers.cpp: In member function 'void ITSUM::up(int, int, int, int, int)':
towers.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
towers.cpp: In member function 'int ITSUM::get(int, int, int, int, int)':
towers.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid = l + r >> 1;
      |             ~~^~~
towers.cpp: In member function 'void ITMAX::up(int, int, int, int, int, int)':
towers.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int mid = l + r >> 1;
      |             ~~^~~
towers.cpp: In member function 'int ITMAX::get(int, int, int, int)':
towers.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l + r >> 1;
      |             ~~^~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:141:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  141 |     mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << j - 1)]);
      |                                                      ~~^~~
towers.cpp:142:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  142 |     mn[j][i] = best(mn[j - 1][i], mn[j - 1][i + (1 << j - 1)]);
      |                                                       ~~^~~
towers.cpp:146:9: warning: unused variable 'tmp' [-Wunused-variable]
  146 |     int tmp = min(getmax(L[i] + 1, i - 1), getmax(i + 1, R[i] - 1)) - h[i];
      |         ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 410700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 191320 KB Output is correct
2 Correct 37 ms 195408 KB Output is correct
3 Correct 38 ms 195472 KB Output is correct
4 Correct 39 ms 195452 KB Output is correct
5 Correct 37 ms 195408 KB Output is correct
6 Correct 38 ms 195800 KB Output is correct
7 Correct 38 ms 195408 KB Output is correct
8 Correct 38 ms 195404 KB Output is correct
9 Correct 38 ms 195564 KB Output is correct
10 Correct 38 ms 195408 KB Output is correct
11 Correct 37 ms 195408 KB Output is correct
12 Correct 35 ms 187216 KB Output is correct
13 Correct 36 ms 195664 KB Output is correct
14 Correct 39 ms 195672 KB Output is correct
15 Correct 38 ms 195416 KB Output is correct
16 Correct 37 ms 195408 KB Output is correct
17 Correct 37 ms 195460 KB Output is correct
18 Correct 37 ms 195408 KB Output is correct
19 Correct 37 ms 195412 KB Output is correct
20 Correct 38 ms 195408 KB Output is correct
21 Correct 38 ms 195416 KB Output is correct
22 Correct 40 ms 195460 KB Output is correct
23 Correct 38 ms 195580 KB Output is correct
24 Correct 39 ms 195672 KB Output is correct
25 Correct 37 ms 193360 KB Output is correct
26 Correct 37 ms 195416 KB Output is correct
27 Correct 37 ms 195552 KB Output is correct
28 Correct 36 ms 195408 KB Output is correct
29 Correct 37 ms 195408 KB Output is correct
30 Correct 38 ms 195548 KB Output is correct
31 Correct 36 ms 195572 KB Output is correct
32 Correct 37 ms 195408 KB Output is correct
33 Correct 37 ms 195404 KB Output is correct
34 Correct 36 ms 195408 KB Output is correct
35 Correct 41 ms 195664 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 191320 KB Output is correct
2 Correct 37 ms 195408 KB Output is correct
3 Correct 38 ms 195472 KB Output is correct
4 Correct 39 ms 195452 KB Output is correct
5 Correct 37 ms 195408 KB Output is correct
6 Correct 38 ms 195800 KB Output is correct
7 Correct 38 ms 195408 KB Output is correct
8 Correct 38 ms 195404 KB Output is correct
9 Correct 38 ms 195564 KB Output is correct
10 Correct 38 ms 195408 KB Output is correct
11 Correct 37 ms 195408 KB Output is correct
12 Correct 35 ms 187216 KB Output is correct
13 Correct 36 ms 195664 KB Output is correct
14 Correct 39 ms 195672 KB Output is correct
15 Correct 38 ms 195416 KB Output is correct
16 Correct 37 ms 195408 KB Output is correct
17 Correct 37 ms 195460 KB Output is correct
18 Correct 37 ms 195408 KB Output is correct
19 Correct 37 ms 195412 KB Output is correct
20 Correct 38 ms 195408 KB Output is correct
21 Correct 38 ms 195416 KB Output is correct
22 Correct 40 ms 195460 KB Output is correct
23 Correct 38 ms 195580 KB Output is correct
24 Correct 39 ms 195672 KB Output is correct
25 Correct 37 ms 193360 KB Output is correct
26 Correct 37 ms 195416 KB Output is correct
27 Correct 37 ms 195552 KB Output is correct
28 Correct 36 ms 195408 KB Output is correct
29 Correct 37 ms 195408 KB Output is correct
30 Correct 38 ms 195548 KB Output is correct
31 Correct 36 ms 195572 KB Output is correct
32 Correct 37 ms 195408 KB Output is correct
33 Correct 37 ms 195404 KB Output is correct
34 Correct 36 ms 195408 KB Output is correct
35 Correct 41 ms 195664 KB Output is correct
36 Runtime error 213 ms 407556 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 409100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 199384 KB Output is correct
2 Runtime error 228 ms 409152 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 191320 KB Output is correct
2 Correct 37 ms 195408 KB Output is correct
3 Correct 38 ms 195472 KB Output is correct
4 Correct 39 ms 195452 KB Output is correct
5 Correct 37 ms 195408 KB Output is correct
6 Correct 38 ms 195800 KB Output is correct
7 Correct 38 ms 195408 KB Output is correct
8 Correct 38 ms 195404 KB Output is correct
9 Correct 38 ms 195564 KB Output is correct
10 Correct 38 ms 195408 KB Output is correct
11 Correct 37 ms 195408 KB Output is correct
12 Correct 35 ms 187216 KB Output is correct
13 Correct 36 ms 195664 KB Output is correct
14 Correct 39 ms 195672 KB Output is correct
15 Correct 38 ms 195416 KB Output is correct
16 Correct 37 ms 195408 KB Output is correct
17 Correct 37 ms 195460 KB Output is correct
18 Correct 37 ms 195408 KB Output is correct
19 Correct 37 ms 195412 KB Output is correct
20 Correct 38 ms 195408 KB Output is correct
21 Correct 38 ms 195416 KB Output is correct
22 Correct 40 ms 195460 KB Output is correct
23 Correct 38 ms 195580 KB Output is correct
24 Correct 39 ms 195672 KB Output is correct
25 Correct 37 ms 193360 KB Output is correct
26 Correct 37 ms 195416 KB Output is correct
27 Correct 37 ms 195552 KB Output is correct
28 Correct 36 ms 195408 KB Output is correct
29 Correct 37 ms 195408 KB Output is correct
30 Correct 38 ms 195548 KB Output is correct
31 Correct 36 ms 195572 KB Output is correct
32 Correct 37 ms 195408 KB Output is correct
33 Correct 37 ms 195404 KB Output is correct
34 Correct 36 ms 195408 KB Output is correct
35 Correct 41 ms 195664 KB Output is correct
36 Runtime error 213 ms 407556 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 410700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -