oj.uz

Submission #850240

# Submission time Handle Problem Language Result Execution time Memory
850240 2023-09-16T07:52:46 Z Tai_xiu Poklon (COCI17_poklon) C++14
140 / 140
 1454 ms 23524 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 4 ms 6744 KB Output is correct
5 Correct 155 ms 10696 KB Output is correct
6 Correct 152 ms 10840 KB Output is correct
7 Correct 400 ms 13384 KB Output is correct
8 Correct 723 ms 17692 KB Output is correct
9 Correct 1036 ms 20104 KB Output is correct
10 Correct 1454 ms 23524 KB Output is correct