oj.uz

Submission #830713

# Submission time Handle Problem Language Result Execution time Memory
830713 2023-08-19T09:45:49 Z NeroZein Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 3380 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

struct SegTree {
  int n;
  vector<int> seg;
  void init (int n_) {
    n = n_; 
    seg.resize(n * 2 - 1);
    build(); 
  }
  void build(int nd, int l, int r) {
    seg[nd] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    build(nd + 1, l, mid);
    build(rs, mid + 1, r); 
  }
  void build() {
    build(0, 0, n - 1); 
  }
  void upd (int nd, int l, int r, int p, int v) {
    if (l == r) {
      seg[nd] = v;
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v);
    } else {
      upd(rs, mid + 1, r, p, v); 
    }
    seg[nd] = max(seg[nd + 1], seg[rs]); 
  }
  void upd(int p, int v) {
    upd(0, 0, n - 1, p, v); 
  }
  int qry (int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) return seg[nd];
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e);
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
      }
    }
  }
  int qry(int s, int e) {
    return qry(0, 0, n - 1, s, e); 
  }
};

vector<int> a; 
vector<int> b; 
SegTree not_matched;
SegTree not_complete;

void init(int N, std::vector<int> H) {
  a = b = H; 
  sort(b.begin(), b.end()); 
  not_matched.init(N); 
  not_complete.init(N); 
}

int get_ind(int value) {
  return upper_bound(b.begin(), b.end(), value) - b.begin() - 1;
}

int get_ind2(int value) {
  return lower_bound(b.begin(), b.end(), value) - b.begin(); 
}

int max_towers(int L, int R, int D) {
  if (L != 0 || R != (int) a.size() - 1) {
    not_complete.build();
    not_matched.build();
    for (int i = L; i <= R; ++i) {
      int match = get_ind(a[i] - D); 
      if (match >= 0) {
        assert(match < (int) a.size()); 
        int best = not_matched.qry(0, match);
        not_complete.upd(get_ind(a[i]), best); 
      }
      int complete = get_ind2(a[i] + D);
      int best = 0;
      if (complete < (int) a.size()) {
        best = not_complete.qry(complete, (int) a.size() - 1); 
      }
      not_matched.upd(get_ind(a[i]), best + 1); 
    }
  }
  return not_matched.seg[0];
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4032 ms 2120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '670', found: '0'
21 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '670', found: '0'
21 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4027 ms 3380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '670', found: '0'
21 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4032 ms 2120 KB Time limit exceeded
2 Halted 0 ms 0 KB -