oj.uz

Submission #523327

# Submission time Handle Problem Language Result Execution time Memory
523327 2022-02-07T13:02:01 Z blue Index (COCI21_index) C++17
110 / 110
 2266 ms 210648 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(R < l || r < L) return 0;
		else if(L <= l && r <= R) return v;
		else return left->rangesum(L, R) + right->rangesum(L, R);
	}

	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 7 ms 7116 KB Output is correct
2 Correct 7 ms 7116 KB Output is correct
3 Correct 7 ms 7116 KB Output is correct
4 Correct 7 ms 7116 KB Output is correct
5 Correct 7 ms 7116 KB Output is correct
6 Correct 8 ms 7084 KB Output is correct
7 Correct 8 ms 7116 KB Output is correct
8 Correct 8 ms 7220 KB Output is correct
9 Correct 7 ms 7116 KB Output is correct
10 Correct 8 ms 7116 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7116 KB Output is correct
2 Correct 7 ms 7116 KB Output is correct
3 Correct 7 ms 7116 KB Output is correct
4 Correct 7 ms 7116 KB Output is correct
5 Correct 7 ms 7116 KB Output is correct
6 Correct 8 ms 7084 KB Output is correct
7 Correct 8 ms 7116 KB Output is correct
8 Correct 8 ms 7220 KB Output is correct
9 Correct 7 ms 7116 KB Output is correct
10 Correct 8 ms 7116 KB Output is correct
11 Correct 311 ms 52652 KB Output is correct
12 Correct 328 ms 52756 KB Output is correct
13 Correct 347 ms 52708 KB Output is correct
14 Correct 352 ms 52664 KB Output is correct
15 Correct 339 ms 52676 KB Output is correct
16 Correct 339 ms 52680 KB Output is correct
17 Correct 345 ms 52776 KB Output is correct
18 Correct 336 ms 52708 KB Output is correct
19 Correct 353 ms 52668 KB Output is correct
20 Correct 326 ms 52648 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7116 KB Output is correct
2 Correct 7 ms 7116 KB Output is correct
3 Correct 7 ms 7116 KB Output is correct
4 Correct 7 ms 7116 KB Output is correct
5 Correct 7 ms 7116 KB Output is correct
6 Correct 8 ms 7084 KB Output is correct
7 Correct 8 ms 7116 KB Output is correct
8 Correct 8 ms 7220 KB Output is correct
9 Correct 7 ms 7116 KB Output is correct
10 Correct 8 ms 7116 KB Output is correct
11 Correct 311 ms 52652 KB Output is correct
12 Correct 328 ms 52756 KB Output is correct
13 Correct 347 ms 52708 KB Output is correct
14 Correct 352 ms 52664 KB Output is correct
15 Correct 339 ms 52676 KB Output is correct
16 Correct 339 ms 52680 KB Output is correct
17 Correct 345 ms 52776 KB Output is correct
18 Correct 336 ms 52708 KB Output is correct
19 Correct 353 ms 52668 KB Output is correct
20 Correct 326 ms 52648 KB Output is correct
21 Correct 2091 ms 210524 KB Output is correct
22 Correct 2065 ms 210564 KB Output is correct
23 Correct 2266 ms 210648 KB Output is correct
24 Correct 2159 ms 210532 KB Output is correct
25 Correct 2150 ms 210568 KB Output is correct
26 Correct 2086 ms 210552 KB Output is correct
27 Correct 2079 ms 210552 KB Output is correct
28 Correct 2227 ms 210608 KB Output is correct
29 Correct 2144 ms 210452 KB Output is correct
30 Correct 2056 ms 210468 KB Output is correct