#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 5e5 + 5, mod = 1e9 + 7; //!
int t, a[N], ans[N], lst[N], tree[N], n;
vector<pii> x[N];
map<int,int> f;
void upd(int id, int t) {
for(id; id <= n; id += id & (-id)) tree[id] += t;
}
int get(int id) {
int ans = 0;
for(id; id >= 1; id -= id & (-id)) ans += tree[id];
return ans;
}
main() {
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
x[l].push_back({r, i});
}
for(int i = n; i >= 1; i--) {
if(f[a[i]]) {
upd(f[a[i]], 1);
if(lst[f[a[i]]]) upd(lst[f[a[i]]], -2) ;
if(lst[lst[f[a[i]]]]) upd(lst[lst[f[a[i]]]], 1);
}
lst[i] = f[a[i]];
f[a[i]] = i;
for(int j = 0; j < x[i].size(); j++) {
ans[x[i][j].s] = get(x[i][j].f);
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
Compilation message
poklon.cpp: In function 'void upd(long long int, long long int)':
poklon.cpp:13:6: warning: statement has no effect [-Wunused-value]
13 | for(id; id <= n; id += id & (-id)) tree[id] += t;
| ^~
poklon.cpp: In function 'long long int get(long long int)':
poklon.cpp:17:6: warning: statement has no effect [-Wunused-value]
17 | for(id; id >= 1; id -= id & (-id)) ans += tree[id];
| ^~
poklon.cpp: At global scope:
poklon.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
20 | main() {
| ^~~~
poklon.cpp: In function 'int main()':
poklon.cpp:40:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = 0; j < x[i].size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12372 KB |
Output is correct |
| 5 |
Correct |
75 ms |
17968 KB |
Output is correct |
| 6 |
Correct |
82 ms |
18000 KB |
Output is correct |
| 7 |
Correct |
245 ms |
23984 KB |
Output is correct |
| 8 |
Correct |
344 ms |
29952 KB |
Output is correct |
| 9 |
Correct |
433 ms |
35800 KB |
Output is correct |
| 10 |
Correct |
574 ms |
41748 KB |
Output is correct |
