#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pii pair<pair<int,int>,int>
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,c[N],cnt[N],a_[N],ans[N],q,n,Block;
string s;
pair<int,int> a[N];
pii p[N];
bool compare(pii a,pii b){
if((a.f.f-1)/Block != (b.f.f-1)/Block) return a.f.f < b.f.f;
return a.f.s < b.f.s;
}
void remove(int u) {
c[cnt[a_[u]]]--;
cnt[a_[u]]--;
c[cnt[a_[u]]]++;
}
void add(int u){
c[cnt[a_[u]]]--;
cnt[a_[u]]++;
c[cnt[a_[u]]]++;
}
main(){
// t=1;
cin>>n>>q;
Block=sqrt(n);
for(int i=1;i<=n;i++){
cin >> a[i].f;
a[i].s = i;
}
sort(a+1,a+n+1);
int idx=0;
for(int i=1;i<=n;i++){
if(a[i].f!=a[i-1].f) idx++;
a_[a[i].s] = idx;
}
for(int i=1;i<=q;i++){
cin >> p[i].f.f >> p[i].f.s;
p[i].s = i;
}
sort(p+1,p+q+1,compare);
int curL = 0 , curR = -1;
for(int i=1;i<=q;i++){
int L = p[i].f.f;
int R = p[i].f.s;
while(curL < L) {
remove(curL);
curL++;
}
while(curL > L){
curL--;
add(curL);
}
while(curR < R){
curR++;
add(curR);
}
while(curR > R){
remove(curR);
curR--;
}
ans[p[i].s] = c[2];
}
for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
}
Compilation message
poklon.cpp:26:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
26 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
4 ms |
332 KB |
Output is correct |
| 4 |
Correct |
17 ms |
612 KB |
Output is correct |
| 5 |
Correct |
525 ms |
5992 KB |
Output is correct |
| 6 |
Correct |
513 ms |
6084 KB |
Output is correct |
| 7 |
Correct |
1244 ms |
11664 KB |
Output is correct |
| 8 |
Runtime error |
83 ms |
10024 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
80 ms |
9940 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
80 ms |
9988 KB |
Execution killed with signal 11 |
