#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
#define int long long
int MAXN=500001;
int s=sqrt(MAXN);
struct query{
int l,r,o;
};
int ans;
unordered_map <int,int> mp;
bool comp(query a,query b){
if(a.l/s==b.l/s){
return a.r<b.r;
}
return a.l/s < b.l/s;
}
void add(int i){
if(mp[i]==2) ans--;
else if(mp[i]==1) ans++;
mp[i]++;
}
void move(int i){
if(mp[i]==2) ans--;
else if(mp[i]==3) ans++;
mp[i]--;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,q;
cin>>n>>q;
int arr[n];
query Q[q];
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=0;i<q;i++){
int L,R;
cin>>L>>R;
Q[i]={L-1,R-1,i};
}
sort(Q,Q+q,comp);
int L=0,R=-1;
int answer[q];
for(int i=0;i<q;i++){
int L1=Q[i].l,R1=Q[i].r;
while(L<L1){
move(arr[L]);
L++;
}
while(L>L1){
L--;
add(arr[L]);
}
while(R<R1){
R++;
add(arr[R]);
}
while(R>R1){
move(arr[R]);
R--;
}
answer[Q[i].o]=ans;
}
for(int i=0;i<q;i++) cout<<answer[i]<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
3 ms |
348 KB |
Output is correct |
| 4 |
Correct |
13 ms |
652 KB |
Output is correct |
| 5 |
Correct |
388 ms |
4356 KB |
Output is correct |
| 6 |
Correct |
406 ms |
4432 KB |
Output is correct |
| 7 |
Correct |
1093 ms |
8536 KB |
Output is correct |
| 8 |
Correct |
2066 ms |
12624 KB |
Output is correct |
| 9 |
Correct |
3111 ms |
16880 KB |
Output is correct |
| 10 |
Correct |
4802 ms |
20820 KB |
Output is correct |
