oj.uz

Submission #393233

# Submission time Handle Problem Language Result Execution time Memory
393233 2021-04-23T02:44:21 Z Talha_Taki Index (COCI21_index) C++17
60 / 110
 2500 ms 47824 KB 
#include <bits/stdc++.h>

#define TIME false

using namespace std;
using namespace std::chrono;

const int MAXN = 2e5;

vector <int> tree[4*MAXN+1];


void build(int now, int l, int r, const vector <int> &arr) {

  if (l == r) {
    tree[now].push_back(arr[l-1]);
    return ;
  }
  int mid = (l+r)>>1;
  int left = now<<1;
  int right = left|1;

  build (left, l, mid, arr);
  build(right, mid+1, r, arr);

  merge(tree[left].begin(), tree[left].end(), tree[right].begin(), tree[right].end(), back_inserter(tree[now]));
}

int query(int now, int l, int r, const int i, const int j, const int x) {
  if (l > j || r < i) return 0;
  if (i <= l && j >= r) {
    int idx = lower_bound(tree[now].begin(), tree[now].end(), x)-tree[now].begin();
    return r-l+1-idx;
  }
  int mid = (l+r)>>1;

  return query(now<<1, l, mid, i, j, x)
        +query(now<<1|1, mid+1, r, i, j, x);
}

int main(int argc, const char* argv[]) {

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);


  int n, q;
  cin >> n >> q;

  vector <int> arr(n);
  for(int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  #if TIME
  double elapsed;
  high_resolution_clock::time_point start = high_resolution_clock::now();
  #endif

  build(1, 1, n, arr);

  while (q--) {
    int l, r;
    cin >> l >> r;

    int left = 1, right = MAXN;
    int best = 0;
    while (left <= right) {
      int x = (left+right)>>1;
      int cnt = query(1, 1, n, l, r, x);

      if (cnt >= x && x >= best) {
        best = x;
        left = x+1;
      }
      else right = x-1;
    }
    cout << best << '\n';
  }

  #if TIME
  high_resolution_clock::time_point finish = high_resolution_clock::now();
  duration<double> time_span = duration_cast<duration<double>>(finish-start);
  elapsed = time_span.count();
  #endif


  //arr.clear();
  //for(int i = 0; i <= (MAXN<<2); ++i) tree[i].clear();

  #if TIME
  cout << fixed << setprecision(10) << elapsed << " seconds\n";
  #endif


  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19148 KB Output is correct
2 Correct 17 ms 19208 KB Output is correct
3 Correct 17 ms 19148 KB Output is correct
4 Correct 17 ms 19208 KB Output is correct
5 Correct 17 ms 19148 KB Output is correct
6 Correct 17 ms 19212 KB Output is correct
7 Correct 18 ms 19212 KB Output is correct
8 Correct 17 ms 19112 KB Output is correct
9 Correct 18 ms 19148 KB Output is correct
10 Correct 20 ms 19276 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19148 KB Output is correct
2 Correct 17 ms 19208 KB Output is correct
3 Correct 17 ms 19148 KB Output is correct
4 Correct 17 ms 19208 KB Output is correct
5 Correct 17 ms 19148 KB Output is correct
6 Correct 17 ms 19212 KB Output is correct
7 Correct 18 ms 19212 KB Output is correct
8 Correct 17 ms 19112 KB Output is correct
9 Correct 18 ms 19148 KB Output is correct
10 Correct 20 ms 19276 KB Output is correct
11 Correct 790 ms 25996 KB Output is correct
12 Correct 799 ms 26052 KB Output is correct
13 Correct 819 ms 26092 KB Output is correct
14 Correct 809 ms 25980 KB Output is correct
15 Correct 801 ms 26024 KB Output is correct
16 Correct 825 ms 25988 KB Output is correct
17 Correct 820 ms 26076 KB Output is correct
18 Correct 817 ms 26208 KB Output is correct
19 Correct 783 ms 26272 KB Output is correct
20 Correct 816 ms 25952 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19148 KB Output is correct
2 Correct 17 ms 19208 KB Output is correct
3 Correct 17 ms 19148 KB Output is correct
4 Correct 17 ms 19208 KB Output is correct
5 Correct 17 ms 19148 KB Output is correct
6 Correct 17 ms 19212 KB Output is correct
7 Correct 18 ms 19212 KB Output is correct
8 Correct 17 ms 19112 KB Output is correct
9 Correct 18 ms 19148 KB Output is correct
10 Correct 20 ms 19276 KB Output is correct
11 Correct 790 ms 25996 KB Output is correct
12 Correct 799 ms 26052 KB Output is correct
13 Correct 819 ms 26092 KB Output is correct
14 Correct 809 ms 25980 KB Output is correct
15 Correct 801 ms 26024 KB Output is correct
16 Correct 825 ms 25988 KB Output is correct
17 Correct 820 ms 26076 KB Output is correct
18 Correct 817 ms 26208 KB Output is correct
19 Correct 783 ms 26272 KB Output is correct
20 Correct 816 ms 25952 KB Output is correct
21 Execution timed out 2592 ms 47824 KB Time limit exceeded
22 Halted 0 ms 0 KB -