oj.uz

답안 #83207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83207 2018-11-06T02:59:23 Z luciocf Poklon (COCI17_poklon) C++14
0 / 140
 1250 ms 13668 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 = 0; 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 = 0; 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 = 0; i < n; i++)
		cin >> num[i];

	compress(n);

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

	sort(q, q+m, comp);

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

	for (int i = 0; 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 = 0; i < m; i++)
		cout << ans[i] << "\n";
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 3 ms 560 KB Output isn't correct
3 Incorrect 3 ms 560 KB Output isn't correct
4 Incorrect 6 ms 940 KB Output isn't correct
5 Incorrect 138 ms 3392 KB Output isn't correct
6 Incorrect 138 ms 3392 KB Output isn't correct
7 Incorrect 353 ms 6168 KB Output isn't correct
8 Incorrect 681 ms 8532 KB Output isn't correct
9 Incorrect 905 ms 11212 KB Output isn't correct
10 Incorrect 1250 ms 13668 KB Output isn't correct