oj.uz

Submission #892763

# Submission time Handle Problem Language Result Execution time Memory
892763 2023-12-25T22:10:33 Z OAleksa Index (COCI21_index) C++14
60 / 110
 1904 ms 56320 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 = 18 * 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 11608 KB Output is correct
2 Correct 4 ms 11608 KB Output is correct
3 Correct 5 ms 11612 KB Output is correct
4 Correct 4 ms 11612 KB Output is correct
5 Correct 4 ms 9564 KB Output is correct
6 Correct 4 ms 11612 KB Output is correct
7 Correct 5 ms 11628 KB Output is correct
8 Correct 4 ms 9564 KB Output is correct
9 Correct 4 ms 11612 KB Output is correct
10 Correct 5 ms 11612 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11608 KB Output is correct
2 Correct 4 ms 11608 KB Output is correct
3 Correct 5 ms 11612 KB Output is correct
4 Correct 4 ms 11612 KB Output is correct
5 Correct 4 ms 9564 KB Output is correct
6 Correct 4 ms 11612 KB Output is correct
7 Correct 5 ms 11628 KB Output is correct
8 Correct 4 ms 9564 KB Output is correct
9 Correct 4 ms 11612 KB Output is correct
10 Correct 5 ms 11612 KB Output is correct
11 Correct 177 ms 20304 KB Output is correct
12 Correct 175 ms 20564 KB Output is correct
13 Correct 177 ms 20336 KB Output is correct
14 Correct 176 ms 20552 KB Output is correct
15 Correct 169 ms 20584 KB Output is correct
16 Correct 165 ms 20344 KB Output is correct
17 Correct 178 ms 20568 KB Output is correct
18 Correct 177 ms 20560 KB Output is correct
19 Correct 179 ms 20364 KB Output is correct
20 Correct 172 ms 20632 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11608 KB Output is correct
2 Correct 4 ms 11608 KB Output is correct
3 Correct 5 ms 11612 KB Output is correct
4 Correct 4 ms 11612 KB Output is correct
5 Correct 4 ms 9564 KB Output is correct
6 Correct 4 ms 11612 KB Output is correct
7 Correct 5 ms 11628 KB Output is correct
8 Correct 4 ms 9564 KB Output is correct
9 Correct 4 ms 11612 KB Output is correct
10 Correct 5 ms 11612 KB Output is correct
11 Correct 177 ms 20304 KB Output is correct
12 Correct 175 ms 20564 KB Output is correct
13 Correct 177 ms 20336 KB Output is correct
14 Correct 176 ms 20552 KB Output is correct
15 Correct 169 ms 20584 KB Output is correct
16 Correct 165 ms 20344 KB Output is correct
17 Correct 178 ms 20568 KB Output is correct
18 Correct 177 ms 20560 KB Output is correct
19 Correct 179 ms 20364 KB Output is correct
20 Correct 172 ms 20632 KB Output is correct
21 Incorrect 1904 ms 56320 KB Output isn't correct
22 Halted 0 ms 0 KB -