#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int n, q;
int a[N], G[N], ans[N], R[N];
map < int , int > f;
vector < pair < int , int > > Q[N];
deque < int > dq[N];
void upd(int x, int vl) {
while (x <= 2 * n) {
G[x] += vl;
x += (x & -x);
}
}
void update(int l, int r, int vl) {
upd(l, vl), upd(r + 1, -vl);
}
int get(int x) {
int res = 0;
while (x > 0) {
res += G[x];
x -= (x & -x);
}
return res;
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> q;
map < int , int > f;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = n; i >= 1; --i) {
if (!f[a[i]])
R[i] = n + 1;
else
R[i] = f[a[i]];
f[a[i]] = i;
}
for (int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
Q[l].push_back({r, i});
}
for (int l = n; l >= 1; --l) {
int x = a[l];
if (dq[x].size() == 2) {
int y = dq[x].front();
update(y, R[y] - 1, -1);
dq[x].pop_front();
}
dq[x].push_back(l);
if (dq[x].size() == 2) {
int y = dq[x].front();
update(y, R[y] - 1, 1);
}
for (int i = 0; i < Q[l].size(); ++i) {
int id = Q[l][i].second;
ans[id] = get(Q[l][i].first);
}
}
for (int i = 1; i <= q; ++i) {
cout << ans[i] << "\n";
}
}
Compilation message
poklon.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
32 | main () {
| ^
poklon.cpp: In function 'int main()':
poklon.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < Q[l].size(); ++i) {
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
342 ms |
524292 KB |
Execution killed with signal 9 |
2 |
Runtime error |
312 ms |
524292 KB |
Execution killed with signal 9 |
3 |
Runtime error |
313 ms |
524292 KB |
Execution killed with signal 9 |
4 |
Runtime error |
315 ms |
524292 KB |
Execution killed with signal 9 |
5 |
Runtime error |
302 ms |
524292 KB |
Execution killed with signal 9 |
6 |
Runtime error |
305 ms |
524292 KB |
Execution killed with signal 9 |
7 |
Runtime error |
303 ms |
524292 KB |
Execution killed with signal 9 |
8 |
Runtime error |
322 ms |
524292 KB |
Execution killed with signal 9 |
9 |
Runtime error |
303 ms |
524292 KB |
Execution killed with signal 9 |
10 |
Runtime error |
309 ms |
524292 KB |
Execution killed with signal 9 |