oj.uz

Submission #40979

# Submission time Handle Problem Language Result Execution time Memory
40979 2018-02-10T18:31:52 Z alenam0161 Poklon (COCI17_poklon) C++14
140 / 140
 1953 ms 17168 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 5e5 + 7;
const int Block = 707;
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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 9 ms 580 KB Output is correct
5 Correct 225 ms 3832 KB Output is correct
6 Correct 203 ms 3848 KB Output is correct
7 Correct 512 ms 7200 KB Output is correct
8 Correct 960 ms 10628 KB Output is correct
9 Correct 1397 ms 14016 KB Output is correct
10 Correct 1953 ms 17168 KB Output is correct