oj.uz

Submission #523328

# Submission time Handle Problem Language Result Execution time Memory
523328 2022-02-07T13:04:52 Z blue Index (COCI21_index) C++17
110 / 110
 2199 ms 207104 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;

struct segtree
{
	int l;
	int r;

	int v = 0;

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r) return;
		int m = (l+r)/2;
		left = new segtree(l, m);
		right = new segtree(m+1, r);
	}

	segtree(int L, int R, int V, segtree* LEFT, segtree* RIGHT)
	{
		l = L, r = R, v = V, left = LEFT, right = RIGHT;
	}

	int rangesum(int L, int R)
	{
		if(L <= l && r <= R) return v;
		else
		{
			int ans = 0;
			if(L <= left->r) ans += left->rangesum(L, R);
			if(R >= right->l) ans += right->rangesum(L, R);
			return ans;
		}
	}

	segtree* add(int I, int V)
	{
		if(I < l || r < I) return this;
		else if(l == r) return new segtree{l, r, v+V, NULL, NULL};
		else
		{
			segtree* new_left = left->add(I, V);
			segtree* new_right = right->add(I, V);
			return new segtree(l, r, v+V, new_left, new_right);
		}
	}
};

const int mx = 200'000;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, q;
	cin >> n >> q;

	segtree* S[1+mx+1];
	S[mx+1] = new segtree(1, n);

	vi p(1+n);
	vi occ[1+mx];
	for(int i = 1; i <= n; i++)
	{
		cin >> p[i];
		occ[p[i]].push_back(i);
	}

	for(int v = mx; v >= 0; v--)
	{
		S[v] = S[v+1];
		for(int i : occ[v])
			S[v] = S[v]->add(i, 1);
	}

	for(int j = 1; j <= q; j++)
	{
		int l, r;
		cin >> l >> r;

		int lo = 0;
		int hi = mx;
		while(lo != hi)
		{
			int mid = (lo+hi)/2 + 1;
			if(S[mid]->rangesum(l, r) >= mid)
				lo = mid;
			else
				hi = mid-1;
		}

		cout << lo << '\n';
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 7 ms 7116 KB Output is correct
3 Correct 7 ms 7216 KB Output is correct
4 Correct 7 ms 7116 KB Output is correct
5 Correct 8 ms 7116 KB Output is correct
6 Correct 8 ms 7224 KB Output is correct
7 Correct 8 ms 7116 KB Output is correct
8 Correct 7 ms 7116 KB Output is correct
9 Correct 7 ms 7116 KB Output is correct
10 Correct 7 ms 7116 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 7 ms 7116 KB Output is correct
3 Correct 7 ms 7216 KB Output is correct
4 Correct 7 ms 7116 KB Output is correct
5 Correct 8 ms 7116 KB Output is correct
6 Correct 8 ms 7224 KB Output is correct
7 Correct 8 ms 7116 KB Output is correct
8 Correct 7 ms 7116 KB Output is correct
9 Correct 7 ms 7116 KB Output is correct
10 Correct 7 ms 7116 KB Output is correct
11 Correct 399 ms 52732 KB Output is correct
12 Correct 331 ms 52692 KB Output is correct
13 Correct 347 ms 52748 KB Output is correct
14 Correct 364 ms 52668 KB Output is correct
15 Correct 335 ms 52760 KB Output is correct
16 Correct 363 ms 52704 KB Output is correct
17 Correct 330 ms 52788 KB Output is correct
18 Correct 345 ms 52704 KB Output is correct
19 Correct 346 ms 52872 KB Output is correct
20 Correct 369 ms 52740 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7116 KB Output is correct
2 Correct 7 ms 7116 KB Output is correct
3 Correct 7 ms 7216 KB Output is correct
4 Correct 7 ms 7116 KB Output is correct
5 Correct 8 ms 7116 KB Output is correct
6 Correct 8 ms 7224 KB Output is correct
7 Correct 8 ms 7116 KB Output is correct
8 Correct 7 ms 7116 KB Output is correct
9 Correct 7 ms 7116 KB Output is correct
10 Correct 7 ms 7116 KB Output is correct
11 Correct 399 ms 52732 KB Output is correct
12 Correct 331 ms 52692 KB Output is correct
13 Correct 347 ms 52748 KB Output is correct
14 Correct 364 ms 52668 KB Output is correct
15 Correct 335 ms 52760 KB Output is correct
16 Correct 363 ms 52704 KB Output is correct
17 Correct 330 ms 52788 KB Output is correct
18 Correct 345 ms 52704 KB Output is correct
19 Correct 346 ms 52872 KB Output is correct
20 Correct 369 ms 52740 KB Output is correct
21 Correct 2128 ms 207088 KB Output is correct
22 Correct 2061 ms 207020 KB Output is correct
23 Correct 2072 ms 207104 KB Output is correct
24 Correct 2127 ms 206904 KB Output is correct
25 Correct 2199 ms 207020 KB Output is correct
26 Correct 2028 ms 207084 KB Output is correct
27 Correct 2005 ms 206824 KB Output is correct
28 Correct 2189 ms 206888 KB Output is correct
29 Correct 1979 ms 206972 KB Output is correct
30 Correct 1940 ms 206840 KB Output is correct