ACM-Practice-Code/C.cpp at master · SegFaultACM/ACM-Practice-Code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#define MAXTEST 100002
int queries[MAXTEST][MAXTEST];
int arr[MAXTEST];
int repetidos[10];
int n;
using namespace std;
void buildMatrix();
int main(){
	int q;
	while(scanf("%d",&n)==1){
		for (int i = 0; i < n; ++i)
		{
			scanf("%d",&arr[i]);
		}
		buildMatrix();
		scanf("%d",&q);
		int init, fin;
		for (int i = 0; i < q; ++i)
		{
			scanf("%d %d",&init, &fin);
			printf("%d\n",queries[init-1][fin-1]);
		}
	}
}
void buildMatrix(){
	queries[0][0] = 1;
	for (int i = 0; i < 10; ++i)
	{
		repetidos[i] = 0;
	}
	repetidos[arr[0]]=1;
	for (int i = 1; i < n; ++i)
	{
		if(repetidos[arr[i]] == 0){
			queries[0][i] = queries[0][i-1]+1;
			repetidos[arr[i]] = 1;
		}else{
			queries[0][i] = queries[0][i-1]	;
			continue;
		}

	}
	for (int i = 1; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			if(i == j){
				queries[i][j] = 1;
			}else{
				if(queries[i-1][j-1]!=queries[i-1][j]){
					queries[i][j] = queries[i][j-1]+1;
				}else{
					queries[i][j] = queries[i][j-1];
				}
			}

		}
	}
}