Submission #393233

#	Time	Username	Problem	Language	Result	Execution time	Memory
393233		Talha_Taki	Index (COCI21_index)	C++17	60 / 110	2592 ms	47824 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50