Submission #40978

#	Time	Username	Problem	Language	Result	Execution time	Memory
40978		alenam0161	Poklon (COCI17_poklon)	C++14	140 / 140	3595 ms	17328 KiB

poklon

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 5e5 + 7;
const int Block = 307;
int cnt[N];
int a[N];
int id[N], timer;
pair<int,int> b[N];
struct ban {
	int l, r, ind;
};
ban Q[N];
int ans = 0;
void add(int x) {
	if (cnt[id[x]] == 1)ans++;
	cnt[id[x]]++;
	if (cnt[id[x]] == 3)ans--;
}
void rem(int x) {
	if (cnt[id[x]] == 2)ans--;
	cnt[id[x]]--;
	if (cnt[id[x]] == 2)ans++;
}
int pat[N];
int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; ++i) { scanf("%d", a + i); b[i] = { a[i],i }; }
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; ++i)if (i == 1 || b[i].first != b[i - 1].first) { id[b[i].second] = ++timer; }
	else { id[b[i].second] = id[b[i - 1].second]; }
	for (int i = 1; i <= q; ++i) {
		int l, r, ind;
		scanf("%d%d", &l, &r);
		ind = i;
		Q[i] = { l,r,ind };
	}
	sort(Q + 1, Q + 1 + q, [&](const ban &a1, const ban &a2){
		if (a1.l / Block == a2.l / Block) {
			return a1.r < a2.r;
		}
		else return a1.l / Block < a2.l / Block;
	});
	int L=0, R=0;
	for (int i = 1; i <= q; ++i) {
//		cout << Q[i].l << " " << Q[i].r << " ID:" << Q[i].ind << endl;
		while (L < Q[i].l)rem(L++);
		while (L > Q[i].l)add(--L);
		while (R < Q[i].r)add(++R);
		while (R > Q[i].r)rem(R--);
		pat[Q[i].ind] = ans;
	}
	for (int i = 1; i <= q; ++i) {
		printf("%d\n", pat[i]);
	}
	return 0;
}

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:31:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
poklon.cpp:32:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; ++i) { scanf("%d", a + i); b[i] = { a[i],i }; }
                                                   ^
poklon.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l, &r);
                        ^

• Subtask 1: 140 / 140