제출 #948637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948637		Am_pula_mare	Poklon (COCI17_poklon)	C++11	140 / 140	1032 ms	13400 KiB

poklon

#include <bits/stdc++.h>

using namespace std;
int const N = 5e5 + 50;
int bucket_size = 0, n, q;
int v[N], M[N];

struct queries{
    int x, y, id, ans;
};
queries Q[N];

bool cmp(queries a, queries b){
    return (a.x / bucket_size) < (b.x / bucket_size) || ((a.x / bucket_size) == (b.x / bucket_size) && a.y <= b.y);
}

bool cmp_id(queries a, queries b){
    return a.id <= b.id;
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];

    for(int i = 1; i <= q; ++i)
    {
        cin >> Q[i].x >> Q[i].y;
        Q[i].id = i;
    }
    bucket_size = (int) (n / sqrt(q));

    sort(Q + 1, Q + q + 1, cmp);
    int l = 0, r = 0, ans = 0;

    for(int i = 1; i <= q; ++i)
    {
        while(r < Q[i].y)
        {
            ++r;
            ++M[v[r]];
            if(M[v[r]] == 2) ++ans;
            if(M[v[r]] == 3) --ans;
        }
        while(l > Q[i].x)
        {
            --l;
            ++M[v[l]];
            if(M[v[l]] == 2) ++ans;
            if(M[v[l]] == 3) --ans;
        }
        while(r > Q[i].y)
        {
            --M[v[r]];
            if(M[v[r]] == 2) ++ans;
            if(M[v[r]] == 1) --ans;
            --r;
        }
        while(l < Q[i].x)
        {
            --M[v[l]];
            if(M[v[l]] == 2) ++ans;
            if(M[v[l]] == 1) --ans;
            ++l;
        }
        Q[i].ans = ans;
    }
    sort(Q + 1, Q + q + 1, cmp_id);

    for(int i = 1; i <= q; ++i)
        cout << Q[i].ans << "\n";
    return 0;
}

• Subtask 1: 140 / 140