Submission #83208

#	Time	Username	Problem	Language	Result	Execution time	Memory
83208		luciocf	Poklon (COCI17_poklon)	C++14	140 / 140	1215 ms	13404 KiB

poklon

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

struct B
{
	int bloco, l, r, ind;
} q[maxn];

int num[maxn], freq[maxn], ans[maxn];

void compress(int n)
{
	vector<int> v;
	map<int, int> mm;

	for (int i = 1; i <= n; i++)
		v.push_back(num[i]);

	sort(v.begin(), v.end());

	int ind = -1;
	for (auto x: v)
		if (mm.find(x) == mm.end())
			mm[x] = ++ind;

	for (int i = 1; i <= n; i++)
		num[i] = mm[num[i]];
}

bool comp(B a, B b)
{
	if (a.bloco == b.bloco) return a.r < b.r;
	return a.bloco < b.bloco;
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	compress(n);

	int bucket = sqrt(n)+1;
	for (int i = 1; i <= m; i++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].bloco = q[i].l/bucket, q[i].ind = i;
	}

	sort(q+1, q+m+1, comp);

	int qtd = 0, l = 1, r = 1;
	freq[num[1]]++;

	for (int i = 1; i <= m; i++)
	{
		while (r > q[i].r)
		{
			freq[num[r]]--;
			if (freq[num[r]] == 1) qtd--;
			if (freq[num[r--]] == 2) qtd++;
		}

		while (r < q[i].r)
		{
			freq[num[++r]]++;
			if (freq[num[r]] == 3) qtd--;
			if (freq[num[r]] == 2) qtd++;
		}

		while (l > q[i].l)
		{
			freq[num[--l]]++;
			if (freq[num[l]] == 3) qtd--;
			if (freq[num[l]] == 2) qtd++;
		}

		while (l < q[i].l)
		{
			freq[num[l]]--;
			if (freq[num[l]] == 1) qtd--;
			if (freq[num[l++]] == 2) qtd++;
		}

		ans[q[i].ind] = qtd;
	}

	for (int i = 1; i <= m; i++)
		cout << ans[i] << "\n";
}

• Subtask 1: 140 / 140