Cod sursa(job #2730500)

Utilizator Data 26 martie 2021 14:11:21 Distincte 35 cpp-64 done Arhiva de probleme 1.4 kb
``````#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream cin ("distincte.in");
ofstream cout ("distincte.out");

const int N = 1e5 + 5;

struct idk  {
int st, dr;
} q[N];

bool cmp(int x, int y)  {
return q[x].dr < q[y].dr;
}

int n, k, m, s;
int a[N], f[N], ans[N];
vector <int> v[320];

int main()  {
cin >> n >> k >> m;
s = sqrt(n);
for (int i = 1; i <= n; ++i)    {
cin >> a[i];
}
for (int i = 1; i <= m; ++i)    {
cin >> q[i].st >> q[i].dr;
v[q[i].st / s].push_back(i);
}
for (int i = 0; i <= n / s; ++i)    {
sort (v[i].begin(), v[i].end(), cmp);
int st = 0, dr = 0, sum = 0;
memset(f, 0, sizeof(f));
for (auto it : v[i])    {
while (dr < q[it].dr)   {
++dr;
if (f[a[dr]] == 0)
sum += a[dr];
++f[a[dr]];
}
while (st < q[it].st)   {
--f[a[st]];
if (f[a[st]] == 0)
sum -= a[st];
++st;
}
while (st > q[it].st)   {
--st;
if (f[a[st]] == 0)
sum += a[st];
++f[a[st]];
}
ans[it] = sum;
}
}
for (int i = 1; i <= m; ++i)
cout << ans[i] << '\n';
return 0;
}
``````