oj.uz

Submission #40976

# Submission time Handle Problem Language Result Execution time Memory
40976 2018-02-10T18:23:42 Z alenam0161 Poklon (COCI17_poklon) C++14
0 / 140
 2110 ms 17136 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) {
		while (L < Q[i].l-1)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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 4 ms 532 KB Output isn't correct
4 Incorrect 10 ms 604 KB Output isn't correct
5 Incorrect 209 ms 3812 KB Output isn't correct
6 Incorrect 210 ms 3928 KB Output isn't correct
7 Incorrect 526 ms 7260 KB Output isn't correct
8 Incorrect 986 ms 10568 KB Output isn't correct
9 Incorrect 1485 ms 14076 KB Output isn't correct
10 Incorrect 2110 ms 17136 KB Output isn't correct