oj.uz

Submission #450428

# Submission time Handle Problem Language Result Execution time Memory
450428 2021-08-02T21:08:28 Z rainboy Poklon (COCI17_poklon) C
140 / 140
 439 ms 29340 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 81 ms 5828 KB Output is correct
6 Correct 75 ms 5884 KB Output is correct
7 Correct 167 ms 11808 KB Output is correct
8 Correct 262 ms 17696 KB Output is correct
9 Correct 351 ms 23464 KB Output is correct
10 Correct 439 ms 29340 KB Output is correct