oj.uz

Submission #892764

# Submission time Handle Problem Language Result Execution time Memory
892764 2023-12-25T22:11:09 Z OAleksa Index (COCI21_index) C++14
110 / 110
 978 ms 60124 KB 
#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 = 19 * 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11100 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 5 ms 9056 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 4 ms 11100 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11100 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 5 ms 9056 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 4 ms 11100 KB Output is correct
11 Correct 186 ms 21748 KB Output is correct
12 Correct 180 ms 22612 KB Output is correct
13 Correct 178 ms 21488 KB Output is correct
14 Correct 181 ms 22612 KB Output is correct
15 Correct 178 ms 22860 KB Output is correct
16 Correct 181 ms 22612 KB Output is correct
17 Correct 180 ms 22584 KB Output is correct
18 Correct 179 ms 22628 KB Output is correct
19 Correct 184 ms 22552 KB Output is correct
20 Correct 171 ms 22472 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11100 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 5 ms 9056 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 4 ms 11100 KB Output is correct
11 Correct 186 ms 21748 KB Output is correct
12 Correct 180 ms 22612 KB Output is correct
13 Correct 178 ms 21488 KB Output is correct
14 Correct 181 ms 22612 KB Output is correct
15 Correct 178 ms 22860 KB Output is correct
16 Correct 181 ms 22612 KB Output is correct
17 Correct 180 ms 22584 KB Output is correct
18 Correct 179 ms 22628 KB Output is correct
19 Correct 184 ms 22552 KB Output is correct
20 Correct 171 ms 22472 KB Output is correct
21 Correct 964 ms 56396 KB Output is correct
22 Correct 958 ms 59660 KB Output is correct
23 Correct 978 ms 59812 KB Output is correct
24 Correct 945 ms 59784 KB Output is correct
25 Correct 968 ms 59788 KB Output is correct
26 Correct 915 ms 59948 KB Output is correct
27 Correct 946 ms 60124 KB Output is correct
28 Correct 903 ms 59480 KB Output is correct
29 Correct 952 ms 60104 KB Output is correct
30 Correct 951 ms 59792 KB Output is correct