#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
const int mxn=5e5,inf=1e9;
int cnt[mxn+10],out[mxn+10],root=250,n,q;
pii v[mxn+10];
bool cmp(ppii a,ppii b){return a.f.s<b.f.s;}
void solve(vector<ppii>g){
if(g.empty())return;
sort(all(g),cmp);
int l=g[0].f.f-1,r=l+1,ans=0;
for(int i=0;i<=n;i++)cnt[i]=0;
for(auto i:g){
while(r<=i.f.s){
cnt[v[r].s]++;
if(cnt[v[r].s]==2)ans++;
if(cnt[v[r].s]==3)ans--;
r++;
}
while(l>i.f.f-1){
cnt[v[l].s]++;
if(cnt[v[l].s]==2)ans++;
if(cnt[v[l].s]==3)ans--;
l--;
}
while(l<i.f.f-1){
l++;
cnt[v[l].s]--;
if(cnt[v[l].s]==1)ans--;
if(cnt[v[l].s]==2)ans++;
if(l==i.f.f-1)break;
}
out[i.s]=ans;
}
}
int32_t main(){
fastio
cin>>n>>q;
vector<int>pos(n);
root=sqrt(n);
for(int i=0;i<n;i++)cin>>v[i].f,pos[i]=v[i].f;
sort(all(pos));
for(int i=0;i<n;i++)v[i].s=lb(all(pos),v[i].f)-pos.begin();
vector<ppii>qry(q);
for(int i=0;i<q;i++){
cin>>qry[i].f.f>>qry[i].f.s,qry[i].s=i;
qry[i].f.f--;
qry[i].f.s--;
}
sort(all(qry));
int cur=0;
for(int i=0;i<n;i+=root){
vector<ppii>tmp;
while(qry[cur].f.f<=i+root&&cur<q)tmp.pb(qry[cur]),cur++;
solve(tmp);
}
for(int i=0;i<q;i++)cout<<out[i]<<'\n';
}
Compilation message
poklon.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
poklon.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
38 | bool cmp(ppii a,ppii b){return a.f.s<b.f.s;}
| ^
poklon.cpp:39:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
39 | void solve(vector<ppii>g){
| ^
poklon.cpp:67:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
67 | int32_t main(){
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4564 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
82 ms |
15496 KB |
Output is correct |
| 6 |
Correct |
90 ms |
15500 KB |
Output is correct |
| 7 |
Correct |
236 ms |
22812 KB |
Output is correct |
| 8 |
Correct |
403 ms |
30036 KB |
Output is correct |
| 9 |
Correct |
552 ms |
35452 KB |
Output is correct |
| 10 |
Correct |
739 ms |
41264 KB |
Output is correct |
