oj.uz

Submission #83208

# Submission time Handle Problem Language Result Execution time Memory
83208 2018-11-06T03:11:59 Z luciocf Poklon (COCI17_poklon) C++14
140 / 140
 1215 ms 13404 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 6 ms 740 KB Output is correct
5 Correct 151 ms 3292 KB Output is correct
6 Correct 139 ms 3292 KB Output is correct
7 Correct 365 ms 5800 KB Output is correct
8 Correct 627 ms 8496 KB Output is correct
9 Correct 904 ms 10900 KB Output is correct
10 Correct 1215 ms 13404 KB Output is correct