#include <bits/stdc++.h>
#define SZ 500005
#define BT 512*1024*2
using namespace std;
typedef pair <int,int> P;
struct segtree
{
int st[BT];
int mum=1;
void init(int n)
{
while(mum<n) mum<<=1;
}
void modify(int v,int l,int r,int i,int x)
{
if(l==r) { st[v]=x; return; }
int m=(l+r)/2;
if(i<=m) modify(v*2+1,l,m,i,x);
else modify(v*2+2,m+1,r,i,x);
st[v]=st[v*2+1]+st[v*2+2];
}
void modify(int i,int v)
{
modify(0,1,mum,i,v);
}
int query(int ql,int qr,int v,int l,int r)
{
if(l>qr||r<ql) return 0;
if(ql<=l&&r<=qr) return st[v];
int m=(l+r)/2;
return query(ql,qr,v*2+1,l,m)+query(ql,qr,v*2+2,m+1,r);
}
int query(int l,int r)
{
return query(l,r,0,1,mum);
}
};
segtree st;
int n,q,a[SZ],ans[SZ];
vector <P> Qs[SZ];
vector <int> pos[SZ];
void compress()
{
vector <int> vec;
for(int i=1;i<=n;i++) vec.push_back(a[i]);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();
}
}
int main()
{
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=q;i++)
{
int l,r;
scanf("%d %d",&l,&r);
Qs[r].push_back(P(l,i));
}
compress();
st.init(n);
for(int i=1;i<=n;i++)
{
int v=a[i];
pos[v].push_back(i);
if(pos[v].size()>=2) st.modify(pos[v][pos[v].size()-2],1);
if(pos[v].size()>=3) st.modify(pos[v][pos[v].size()-3],-1);
if(pos[v].size()>=4) st.modify(pos[v][pos[v].size()-4],0);
for(auto qq:Qs[i]) ans[qq.second]=st.query(qq.first,i);
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
poklon.cpp:57:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | for(int i=1;i<=n;i++) scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
poklon.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d %d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23792 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
16 ms |
24052 KB |
Output is correct |
| 5 |
Correct |
117 ms |
28080 KB |
Output is correct |
| 6 |
Correct |
119 ms |
28140 KB |
Output is correct |
| 7 |
Correct |
282 ms |
32440 KB |
Output is correct |
| 8 |
Correct |
426 ms |
37240 KB |
Output is correct |
| 9 |
Correct |
561 ms |
41576 KB |
Output is correct |
| 10 |
Correct |
730 ms |
45248 KB |
Output is correct |
