#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 = 2e5 + 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) ;
}
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:39: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]
39 | for(int j = 0; j < x[i].size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
5036 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
5332 KB |
Output isn't correct |
| 5 |
Incorrect |
62 ms |
12776 KB |
Output isn't correct |
| 6 |
Incorrect |
84 ms |
12960 KB |
Output isn't correct |
| 7 |
Incorrect |
187 ms |
21132 KB |
Output isn't correct |
| 8 |
Runtime error |
23 ms |
14124 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
20 ms |
14088 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
20 ms |
14116 KB |
Execution killed with signal 11 |
