Submission #1153998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153998		YSH2020	Index (COCI21_index)	C++20	110 / 110	622 ms	6272 KiB

index

#include <bits/stdc++.h>
using namespace std;
int ft[400005], X;
int qry(int idx) {
  int ans = 0;
  for (; idx > 0; idx -= idx&(-idx)) ans += ft[idx];
  return ans;
}
void add(int idx, int v) {
  for(; idx <= X; idx += (idx&-idx)) ft[idx] += v;
}
const int N = 500;
bool comp(pair<pair<int, int>,int> x, pair<pair<int, int>,int> y) {
  return make_pair(x.first.first/N, x.first.second) < make_pair(y.first.first/N, y.first.second);
}

int main() {
  X = 200001;
  int n; cin >> n;
  int q; cin >> q;
  int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
  int ans[q];
  vector<pair<pair<int, int>, int>> queries(q);
  for (int i = 0; i < q; i++) {
    int s, e; cin >> s >> e;
    s--;e--;
    queries[i] = {{s, e}, i};
  }
  sort(queries.begin(), queries.end(), comp);
  int curL = 0;
  int curR = -1;
  multiset<int> s;
  for (auto x:queries) {
    while (curL < x.first.first) {
      add(a[curL], -1);
      curL++;
    }
    while (curL > x.first.first) {
      curL--;
      add(a[curL], 1);
    }
    while (curR < x.first.second) {
      curR++;
      add(a[curR], 1);
    }
    while (curR > x.first.second) {
      add(a[curR], -1);
      curR--;
    }
    int l = 0;
    int r = 200005;
    while (r-l > 1) {
      int mid = (r+l)/2;
      if (x.first.second-x.first.first+1-qry(mid-1) >= mid) l = mid;
      else r = mid;
    }
    ans[x.second] = l;
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

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