oj.uz

Submission #970655

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

const int N = 1e5 + 10, S = 1e5 * 20 * 2;

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

int n;

vector<int> rrh, pos[2 * 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[2 * 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[2 * 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 Correct 397 ms 171636 KB Output is correct
2 Runtime error 274 ms 354328 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 162648 KB Output is correct
2 Correct 31 ms 162656 KB Output is correct
3 Correct 32 ms 163156 KB Output is correct
4 Correct 32 ms 162688 KB Output is correct
5 Correct 32 ms 162636 KB Output is correct
6 Correct 31 ms 162648 KB Output is correct
7 Correct 31 ms 162640 KB Output is correct
8 Correct 31 ms 162580 KB Output is correct
9 Correct 31 ms 162648 KB Output is correct
10 Correct 31 ms 162876 KB Output is correct
11 Correct 31 ms 162648 KB Output is correct
12 Correct 29 ms 158296 KB Output is correct
13 Correct 32 ms 162648 KB Output is correct
14 Correct 30 ms 162652 KB Output is correct
15 Correct 32 ms 162640 KB Output is correct
16 Correct 31 ms 162640 KB Output is correct
17 Correct 35 ms 162640 KB Output is correct
18 Correct 34 ms 162640 KB Output is correct
19 Correct 33 ms 162640 KB Output is correct
20 Correct 32 ms 162640 KB Output is correct
21 Correct 31 ms 162648 KB Output is correct
22 Correct 31 ms 162724 KB Output is correct
23 Correct 32 ms 162648 KB Output is correct
24 Correct 30 ms 162644 KB Output is correct
25 Correct 30 ms 162648 KB Output is correct
26 Correct 30 ms 162640 KB Output is correct
27 Correct 31 ms 162904 KB Output is correct
28 Correct 31 ms 162640 KB Output is correct
29 Correct 32 ms 162676 KB Output is correct
30 Correct 31 ms 162640 KB Output is correct
31 Correct 31 ms 162640 KB Output is correct
32 Correct 33 ms 162648 KB Output is correct
33 Correct 31 ms 162640 KB Output is correct
34 Correct 31 ms 162640 KB Output is correct
35 Correct 30 ms 162648 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 162648 KB Output is correct
2 Correct 31 ms 162656 KB Output is correct
3 Correct 32 ms 163156 KB Output is correct
4 Correct 32 ms 162688 KB Output is correct
5 Correct 32 ms 162636 KB Output is correct
6 Correct 31 ms 162648 KB Output is correct
7 Correct 31 ms 162640 KB Output is correct
8 Correct 31 ms 162580 KB Output is correct
9 Correct 31 ms 162648 KB Output is correct
10 Correct 31 ms 162876 KB Output is correct
11 Correct 31 ms 162648 KB Output is correct
12 Correct 29 ms 158296 KB Output is correct
13 Correct 32 ms 162648 KB Output is correct
14 Correct 30 ms 162652 KB Output is correct
15 Correct 32 ms 162640 KB Output is correct
16 Correct 31 ms 162640 KB Output is correct
17 Correct 35 ms 162640 KB Output is correct
18 Correct 34 ms 162640 KB Output is correct
19 Correct 33 ms 162640 KB Output is correct
20 Correct 32 ms 162640 KB Output is correct
21 Correct 31 ms 162648 KB Output is correct
22 Correct 31 ms 162724 KB Output is correct
23 Correct 32 ms 162648 KB Output is correct
24 Correct 30 ms 162644 KB Output is correct
25 Correct 30 ms 162648 KB Output is correct
26 Correct 30 ms 162640 KB Output is correct
27 Correct 31 ms 162904 KB Output is correct
28 Correct 31 ms 162640 KB Output is correct
29 Correct 32 ms 162676 KB Output is correct
30 Correct 31 ms 162640 KB Output is correct
31 Correct 31 ms 162640 KB Output is correct
32 Correct 33 ms 162648 KB Output is correct
33 Correct 31 ms 162640 KB Output is correct
34 Correct 31 ms 162640 KB Output is correct
35 Correct 30 ms 162648 KB Output is correct
36 Correct 130 ms 171400 KB Output is correct
37 Correct 216 ms 174192 KB Output is correct
38 Correct 214 ms 174104 KB Output is correct
39 Correct 200 ms 173616 KB Output is correct
40 Correct 201 ms 173580 KB Output is correct
41 Correct 210 ms 173588 KB Output is correct
42 Correct 231 ms 173792 KB Output is correct
43 Correct 109 ms 175248 KB Output is correct
44 Correct 111 ms 175632 KB Output is correct
45 Runtime error 259 ms 355092 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 174120 KB Output is correct
2 Correct 952 ms 174108 KB Output is correct
3 Correct 972 ms 174268 KB Output is correct
4 Correct 983 ms 173744 KB Output is correct
5 Correct 977 ms 173688 KB Output is correct
6 Correct 990 ms 173580 KB Output is correct
7 Correct 1016 ms 173740 KB Output is correct
8 Correct 715 ms 175248 KB Output is correct
9 Correct 726 ms 175504 KB Output is correct
10 Runtime error 309 ms 354656 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 168412 KB Output is correct
2 Correct 922 ms 174268 KB Output is correct
3 Correct 917 ms 174100 KB Output is correct
4 Correct 889 ms 173536 KB Output is correct
5 Correct 859 ms 173848 KB Output is correct
6 Correct 907 ms 173540 KB Output is correct
7 Correct 892 ms 173580 KB Output is correct
8 Correct 681 ms 175252 KB Output is correct
9 Correct 763 ms 175632 KB Output is correct
10 Incorrect 736 ms 175220 KB 5th lines differ - on the 1st token, expected: '1', found: '2'
11 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 162648 KB Output is correct
2 Correct 31 ms 162656 KB Output is correct
3 Correct 32 ms 163156 KB Output is correct
4 Correct 32 ms 162688 KB Output is correct
5 Correct 32 ms 162636 KB Output is correct
6 Correct 31 ms 162648 KB Output is correct
7 Correct 31 ms 162640 KB Output is correct
8 Correct 31 ms 162580 KB Output is correct
9 Correct 31 ms 162648 KB Output is correct
10 Correct 31 ms 162876 KB Output is correct
11 Correct 31 ms 162648 KB Output is correct
12 Correct 29 ms 158296 KB Output is correct
13 Correct 32 ms 162648 KB Output is correct
14 Correct 30 ms 162652 KB Output is correct
15 Correct 32 ms 162640 KB Output is correct
16 Correct 31 ms 162640 KB Output is correct
17 Correct 35 ms 162640 KB Output is correct
18 Correct 34 ms 162640 KB Output is correct
19 Correct 33 ms 162640 KB Output is correct
20 Correct 32 ms 162640 KB Output is correct
21 Correct 31 ms 162648 KB Output is correct
22 Correct 31 ms 162724 KB Output is correct
23 Correct 32 ms 162648 KB Output is correct
24 Correct 30 ms 162644 KB Output is correct
25 Correct 30 ms 162648 KB Output is correct
26 Correct 30 ms 162640 KB Output is correct
27 Correct 31 ms 162904 KB Output is correct
28 Correct 31 ms 162640 KB Output is correct
29 Correct 32 ms 162676 KB Output is correct
30 Correct 31 ms 162640 KB Output is correct
31 Correct 31 ms 162640 KB Output is correct
32 Correct 33 ms 162648 KB Output is correct
33 Correct 31 ms 162640 KB Output is correct
34 Correct 31 ms 162640 KB Output is correct
35 Correct 30 ms 162648 KB Output is correct
36 Correct 130 ms 171400 KB Output is correct
37 Correct 216 ms 174192 KB Output is correct
38 Correct 214 ms 174104 KB Output is correct
39 Correct 200 ms 173616 KB Output is correct
40 Correct 201 ms 173580 KB Output is correct
41 Correct 210 ms 173588 KB Output is correct
42 Correct 231 ms 173792 KB Output is correct
43 Correct 109 ms 175248 KB Output is correct
44 Correct 111 ms 175632 KB Output is correct
45 Runtime error 259 ms 355092 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 171636 KB Output is correct
2 Runtime error 274 ms 354328 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -