Submission #1342630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342630		trungcan	Poklon (COCI17_poklon)	C++20	140 / 140	686 ms	15036 KiB

poklon

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5, B = 700;

int n, Q, ans[N];
int a[N], cnt[N], cur;
vector<int> v;

struct can{
    int l, r, id;
} q[N];

bool cmp(can x, can y){
    if ((x.l - 1) / B == (y.l - 1) / B)
        return ((x.l - 1) / B) & 1 ? x.r > y.r : x.r < y.r;
    return x.l < y.l;
}

void add(int i){
    int &x = cnt[a[i]];
    ++x;
    if (x == 2) ++cur;
    if (x == 3) --cur;
}

void del(int i){
    int &x = cnt[a[i]];
    --x;
    if (x == 2) ++cur;
    if (x == 1) --cur;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> Q;
    for (int i = 1; i <= n; ++i) cin >> a[i], v.push_back(a[i]);

    sort(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();

    for (int i = 1; i <= Q; ++i) cin >> q[i].l >> q[i].r, q[i].id = i;
    sort(q + 1, q + Q + 1, cmp);

    int L = 1, R = 0;
    for (int i = 1; i <= Q; ++i){
        while (R < q[i].r) add(++R);
        while (R > q[i].r) del(R--);
        while (L < q[i].l) del(L++);
        while (L > q[i].l) add(--L);

        ans[q[i].id] = cur;
    }

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

• Subtask 1: 140 / 140