Submission #892762

#	Time	Username	Problem	Language	Result	Execution time	Memory
892762		OAleksa	Index (COCI21_index)	C++14	60 / 110	206 ms	103508 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
const int N = 2e5 + 69;
const int M = 17 * N;
int n, q, a[N];
int st[M], root[N], lc[M], rc[M], node;
vector<int> pos[N];
void modify(int v, int rt, int tl, int tr, int p) {
	if (tl == tr)
		st[v] = 1;
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid) {
			lc[v] = ++node;
			rc[v] = rc[rt];
			modify(lc[v], lc[rt], tl, mid, p);
		}
		else {
			rc[v] = ++node;
			lc[v] = lc[rt];
			modify(rc[v], rc[rt], mid + 1, tr, p);
		}
		st[v] = st[lc[v]] + st[rc[v]];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return get(lc[v], tl, mid, l, r) + get(rc[v], mid + 1, tr, l, r);
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
  cout.tie(nullptr); 
  cin.tie(nullptr);
  //freopen("newbarn.in", "r", stdin);
  //freopen(newbarn.out", "w", stdout);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> q;
  	for (int i = 1;i <= n;i++) {
  		cin >> a[i];
  		pos[a[i]].push_back(i);
  	}
  	for (int i = N - 1;i >= 1;i--) {
  		root[i] = root[i + 1];
  		for (auto u : pos[i]) {
  			int nr = ++node;
  			modify(nr, root[i], 1, n, u);
  			root[i] = nr;
  		}
  	}
  	while (q--) {
  		int x, y;
  		cin >> x >> y;
  		int l = 1, r = N - 1, ans = 0;
  		while (l <= r) {
  			int mid = (l + r) / 2;
  			int g = get(root[mid], 1, n, x, y);
  			if (g >= mid) {
  				ans = mid;
  				l = mid + 1;
  			}
  			else
  				r = mid - 1;
  		}
  		cout << ans << '\n';
  	}
  }
  return 0;
}

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