Submission #787228

#	Time	Username	Problem	Language	Result	Execution time	Memory
787228		tvladm2009	Index (COCI21_index)	C++17	110 / 110	685 ms	9872 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int BS = 448;
int a[N], aib[N];

void add(int i, int x) {
  while (i < N) {
    aib[i] += x;
    i += i & (-i);
  }
}

int get(int i) {
  int sol = 0;
  while (i) {
    sol += aib[i];
    i -= i & (-i);
  }
  return sol;
}

struct Query {
  int l;
  int r;
  int id;
};

bool operator < (Query a, Query b) {
  return a.l / BS < b.l / BS || (a.l / BS == b.l / BS && a.r < b.r);
}

Query queries[N];
int sol[N];
int n, q;

void expand(int x) {
  add(a[x], +1);
}

void contract(int x) {
  add(a[x], -1);
}

void Mo() {
  int l = 1, r = 0;
  for (int i = 1; i <= q; i++) {
    int ql = queries[i].l;
    int qr = queries[i].r;
    while (l > ql) {
      l--;
      expand(l);
    }
    while (r < qr) {
      r++;
      expand(r);
    }
    while (l < ql) {
      contract(l);
      l++;
    }
    while (r > qr) {
      contract(r);
      r--;
    }
    int low = 1, high = N - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if ((qr - ql + 1) - get(mid - 1) >= mid) {
        low = mid + 1;
        sol[queries[i].id] = mid;
      } else {
        high = mid - 1;
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; i++) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].id = i;
  }
  sort(queries + 1, queries + q + 1);
  Mo();
  for (int i = 1; i <= q; i++) {
    cout << sol[i] << "\n";
  }
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50