Submission #850240

#	Time	Username	Problem	Language	Result	Execution time	Memory
850240		Tai_xiu	Poklon (COCI17_poklon)	C++14	140 / 140	1454 ms	23524 KiB

poklon

#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,m,block_size  ;
struct query
{
    int l,r,idx;
    bool operator < (query other) const{
        return make_pair((l-1)/block_size,r) < make_pair (( other.l-1)/block_size,other.r);
    }
}q[maxn];
int nho[maxn],cnt=0,ans[maxn],a[maxn];
void add (int i)
{
    ++nho[a[i]];
    if  (nho[a[i]]==2)
        ++cnt;
    if (nho[a[i]]==3)
        --cnt;
}
void remove(int i)
{
    --nho[a[i]];
    if (nho[a[i]]==2)
        ++cnt;
    if (nho[a[i]]==1)
        --cnt;
}
int tmp[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    block_size=sqrt(n);
    if (block_size*block_size<n)
        block_size++;
    int x,y;
    for (int i=1;i<=m;i++){
        cin>>x>>y;
        q[i].l=x;
        q[i].r=y;
        q[i].idx=i;
    }
    sort (q+1,q+m+1);
    for (int i=1;i<=n;i++)
        tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);
    for (int i=1;i<=n;i++)
        a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
    int curr_l=1,curr_r=0;
    for (int i=1;i<=m;++i){
        int L=q[i].l,R=q[i].r,id=q[i].idx;
        while (curr_l>L)
            add(--curr_l);
        while (curr_r<R)
            add(++curr_r);
        while (curr_l<L)
            remove(curr_l++);
        while (curr_r>R)
            remove(curr_r--);
        ans[id]=cnt;
    }
    for (int i=1;i<=m;i++)
        cout<<ans[i]<<'\n';

}

• Subtask 1: 140 / 140