oj.uz

Submission #892762

# Submission time Handle Problem Language Result Execution time Memory
892762 2023-12-25T22:10:12 Z OAleksa Index (COCI21_index) C++14
60 / 110
 206 ms 103508 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 = 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9560 KB Output is correct
2 Correct 4 ms 9564 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 5 ms 9648 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 4 ms 9564 KB Output is correct
7 Correct 4 ms 9708 KB Output is correct
8 Correct 4 ms 7520 KB Output is correct
9 Correct 4 ms 9564 KB Output is correct
10 Correct 4 ms 9564 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9560 KB Output is correct
2 Correct 4 ms 9564 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 5 ms 9648 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 4 ms 9564 KB Output is correct
7 Correct 4 ms 9708 KB Output is correct
8 Correct 4 ms 7520 KB Output is correct
9 Correct 4 ms 9564 KB Output is correct
10 Correct 4 ms 9564 KB Output is correct
11 Correct 173 ms 21636 KB Output is correct
12 Correct 171 ms 23036 KB Output is correct
13 Correct 190 ms 21788 KB Output is correct
14 Correct 206 ms 23036 KB Output is correct
15 Correct 175 ms 23056 KB Output is correct
16 Correct 182 ms 23040 KB Output is correct
17 Correct 173 ms 23312 KB Output is correct
18 Correct 177 ms 22892 KB Output is correct
19 Correct 189 ms 23260 KB Output is correct
20 Correct 177 ms 22940 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9560 KB Output is correct
2 Correct 4 ms 9564 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 5 ms 9648 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 4 ms 9564 KB Output is correct
7 Correct 4 ms 9708 KB Output is correct
8 Correct 4 ms 7520 KB Output is correct
9 Correct 4 ms 9564 KB Output is correct
10 Correct 4 ms 9564 KB Output is correct
11 Correct 173 ms 21636 KB Output is correct
12 Correct 171 ms 23036 KB Output is correct
13 Correct 190 ms 21788 KB Output is correct
14 Correct 206 ms 23036 KB Output is correct
15 Correct 175 ms 23056 KB Output is correct
16 Correct 182 ms 23040 KB Output is correct
17 Correct 173 ms 23312 KB Output is correct
18 Correct 177 ms 22892 KB Output is correct
19 Correct 189 ms 23260 KB Output is correct
20 Correct 177 ms 22940 KB Output is correct
21 Runtime error 147 ms 103508 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -