#include <iostream>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500000
int n, q, a[N], p[N], d[N], t[N+1], e[N];
array<int, 3> b[N];
void compress()
{
int c[N], C = n;
memcpy(c, a, n * sizeof *a);
sort(c, c+C);
for (int i = 0; i < n; ++i) a[i] = lower_bound(c, c+C, a[i]) - c;
}
void upd(int p, int k) { for (; p <= N; p+=p&-p) t[p]+=k; }
int qry(int p){ int z{0};for(;p;p-=p&-p) z+=t[p];return z;}
int main()
{
ShinLena;
cin >> n >> q;
for (int i = 0; i < n; ++i) cin >> a[i];
compress();
for (int i = 0; i < q; ++i) cin >> b[i][0] >> b[i][1], b[i][2] = i;
sort(b, b+q);
for (int j = q - 1, i = n; i--;)
{
if (d[a[i]])
{
upd(d[a[i]]+1, 1);
if (p[d[a[i]]]) upd(p[d[a[i]]]+1, -2);
p[i] = d[a[i]];
}
for (; j >= 0 && b[j][0] == i + 1; --j) e[b[j][2]] = qry(b[j][1]);
d[a[i]] = i;
}
for (int i = 0; i < q; ++i) cout << e[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 5 |
Incorrect |
47 ms |
12056 KB |
Output isn't correct |
| 6 |
Incorrect |
54 ms |
12180 KB |
Output isn't correct |
| 7 |
Incorrect |
107 ms |
14864 KB |
Output isn't correct |
| 8 |
Incorrect |
166 ms |
17840 KB |
Output isn't correct |
| 9 |
Incorrect |
224 ms |
19796 KB |
Output isn't correct |
| 10 |
Incorrect |
279 ms |
21912 KB |
Output isn't correct |
