Submission #450428

#	Time	Username	Problem	Language	Result	Execution time	Memory
450428		rainboy	Poklon (COCI17_poklon)	C11	140 / 140	439 ms	29340 KiB

poklon

#include <stdio.h>
#include <string.h>

#define N	500000
#define Q	500000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *xx;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int ft[N];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int aa[N], ii[N], ii1[N], ii2[N], ii3[N], ll[Q], rr[Q], hh[Q], ans[Q];
	int n, q, h, i, a;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ii[i] = i;
	}
	xx = aa, sort(ii, 0, n);
	for (i = 0, a = 0; i < n; i++)
		aa[ii[i]] = i + 1 == n || aa[ii[i + 1]] != aa[ii[i]] ? a++ : a;
	for (h = 0; h < q; h++) {
		scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
		hh[h] = h;
	}
	xx = rr, sort(hh, 0, q);
	memset(ii1, -1, n * sizeof *ii1), memset(ii2, -1, n * sizeof *ii2), memset(ii3, -1, n * sizeof *ii3);
	for (i = 0, h = 0; i < n; i++) {
		a = aa[i];
		if (ii3[a] != -1)
			update(ii3[a], n, 1);
		if (ii2[a] != -1)
			update(ii2[a], n, -2);
		if (ii1[a] != -1)
			update(ii1[a], n, 1);
		ii3[a] = ii2[a], ii2[a] = ii1[a], ii1[a] = i;
		while (h < q && rr[hh[h]] == i) {
			int h_ = hh[h++];

			ans[h_] = query(rr[h_]) - query(ll[h_] - 1);
		}
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

poklon.c: In function 'main':
poklon.c:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
poklon.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
poklon.c:66:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140