oj.uz

답안 #83206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83206 2018-11-06T02:58:25 Z luciocf Poklon (COCI17_poklon) C++14
0 / 140
 5000 ms 41128 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.ind%2 ? a.r > b.r : 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 9 ms 6264 KB Output isn't correct
2 Incorrect 2 ms 6264 KB Output isn't correct
3 Incorrect 3 ms 6264 KB Output isn't correct
4 Incorrect 18 ms 6876 KB Output isn't correct
5 Incorrect 951 ms 10004 KB Output isn't correct
6 Incorrect 841 ms 11616 KB Output isn't correct
7 Incorrect 2982 ms 16556 KB Output isn't correct
8 Execution timed out 5022 ms 19240 KB Time limit exceeded
9 Execution timed out 5032 ms 31064 KB Time limit exceeded
10 Execution timed out 5020 ms 41128 KB Time limit exceeded