#include <bits/stdc++.h>
#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
int n,q;
struct meh{
int a,b,c;
};
int num=sqrt(2e5);
bool cmp(meh a,meh b){
if(a.a/num<b.a/num) return 1;
else if(a.a/num>b.a/num) return 0;
else{
if(a.b<b.b) return 1;
else if(a.b>b.b) return 0;
else return 1;
}
}
int arr[200005];
unordered_map<int,int>mp;
int ans=0;
meh qu[200005];
void add(int val){
mp[val]++;
if(mp[val]==1) ans++;
}
void remo(int val){
mp[val]--;
if(mp[val]==0) ans--;
}
int anss[200005];
void solve(){
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<q;i++){
cin>>qu[i].a>>qu[i].b;
qu[i].a--,qu[i].b--;
qu[i].c=i;
}
sort(qu,qu+q,cmp);
int l,r;
l=0;
r=-1;
for(int i=0;i<q;i++){
while(l<qu[i].a){
remo(arr[l]);
l++;
}
while(l>qu[i].a){
l--;
add(arr[l]);
}
while(r<qu[i].b){
r++;
add(arr[r]);
}
while(r>qu[i].b){
remo(arr[r]);
r--;
}
anss[qu[i].c]=ans;
}
for(int i=0;i<q;i++){
co anss[i]<<'\n';
}
}
int main()
{
suiii
ll t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 4 |
Incorrect |
7 ms |
2644 KB |
Output isn't correct |
| 5 |
Incorrect |
268 ms |
3324 KB |
Output isn't correct |
| 6 |
Incorrect |
268 ms |
3412 KB |
Output isn't correct |
| 7 |
Incorrect |
882 ms |
5148 KB |
Output isn't correct |
| 8 |
Incorrect |
10 ms |
3160 KB |
Output isn't correct |
| 9 |
Incorrect |
9 ms |
3164 KB |
Output isn't correct |
| 10 |
Incorrect |
11 ms |
3160 KB |
Output isn't correct |
