#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
struct Fenwick{
vector<int>bit;
int size;
void modify(int j,int v){
for(;j<size;j+=j&-j)bit[j]+=v;
}
int query(int j){
int v=0;
for(;j>0;j-=j&-j)v+=bit[j];
return v;
}
Fenwick(int n){
bit=vector<int>(n,0);
size=n;
}
};
vector<pair<ii,int>>off[500005];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int n,q;
cin>>n>>q;
vector<int>arr(n+1);
vector<pair<ii,int>>Q;
vector<int>ans(q);
map<int,map<int,int>>L,R;
for(int i=1;i<=n;i++){
cin>>arr[i];
L[arr[i]][i]=0;
R[arr[i]][i]=n+1;
}
for(int i=0;i<q;i++){
int x,y;
cin>>x>>y;
Q.pb({{x,y},i});
}
sort(all(Q));
for(map<int,map<int,int>>::iterator it=L.begin();it!=L.end();it++){
for(map<int,int>::iterator itr=++it->second.begin();itr!=it->second.end();itr++){
itr->second=prev(itr)->first;
}
}
for(map<int,map<int,int>>::iterator it=R.begin();it!=R.end();it++){
for(map<int,int>::iterator itr=--it->second.end();itr!=it->second.begin();itr--){
prev(itr)->second=itr->first;
}
}
for(map<int,map<int,int>>::iterator it=L.begin();it!=L.end();it++){
int x=it->first;
for(map<int,int>::iterator itr=it->second.begin();itr!=it->second.end();itr++){
int ind=itr->first;
int l=itr->second;
int r=R[x][ind];
if(r==n+1)continue;
int rr=R[x][r];
off[l+1].pb({{r,rr},1});
off[ind+1].pb({{r,rr},-1});
}
}
Fenwick data(500005);
int ind=0;
for(int i=0;i<=n;i++){
for(int j=0;j<off[i].size();j++){
data.modify(off[i][j].first.first,off[i][j].second);
data.modify(off[i][j].first.second,-off[i][j].second);
}
while(ind<q&&Q[ind].first.first==i){
ans[Q[ind].second]=data.query(Q[ind].first.second);
ind++;
}
}
for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}
Compilation message
poklon.cpp: In function 'int32_t main()':
poklon.cpp:78:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<off[i].size();j++){
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
14072 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14072 KB |
Output is correct |
| 3 |
Correct |
16 ms |
14200 KB |
Output is correct |
| 4 |
Correct |
26 ms |
14812 KB |
Output is correct |
| 5 |
Correct |
240 ms |
30240 KB |
Output is correct |
| 6 |
Correct |
254 ms |
30268 KB |
Output is correct |
| 7 |
Correct |
578 ms |
47012 KB |
Output is correct |
| 8 |
Correct |
939 ms |
63468 KB |
Output is correct |
| 9 |
Correct |
1240 ms |
79808 KB |
Output is correct |
| 10 |
Correct |
1597 ms |
96308 KB |
Output is correct |
