Pagini recente » Cod sursa (job #164929) | Cod sursa (job #1102876) | Cod sursa (job #1012382) | Cod sursa (job #1664896) | Cod sursa (job #265570)
Cod sursa(job #265570)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned int I;
int n;
int idx = 0;
vector<I> Hash[1000000];
vector<int> id[1000000];
const int M = 999983;
int v[1 << 20];
int diva[(1<<20)+1];
int A, B, N;
int findIdx(I X) {
int key = X % M;
for (int i = 0; i < Hash[key].size(); ++i) if (Hash[key][i] == X) return id[key][i];
return -1;
}
void addHash(I X) {
int key = X % M;
Hash[key].push_back(X);
id[key].push_back(idx);
++idx;
}
typedef long long LL;
LL findA(I A) {
//sub lungime A
if (A == 0) return 0;
int distincte = 0;
int left = 0;
LL total = 0;
for (int i = 0; i < N; ++i) {
if (!diva[v[i]]) {++distincte;}
++diva[v[i]];
//adjust left
while (left < i && distincte > A) {
if (--diva[v[left++]] == 0) --distincte;
}
total+= i - left + 1;
}
while (left < N) {--diva[v[left++]];}
return total;
}
int main() {
ifstream fin("secv5.in");
ofstream fout("secv5.out");
fin >> N >> A >> B;
for (int i = 0; i < N; ++i) {
I X;
fin >> X;
v[i] = findIdx(X);
if (v[i] == -1) { v[i] = idx; addHash(X); }
}
fout << findA(B) - findA(A-1) << '\n';
return 0;
}