Submission #523328

#	Time	Username	Problem	Language	Result	Execution time	Memory
523328		blue	Index (COCI21_index)	C++17	110 / 110	2199 ms	207104 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50