제출 #1330805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1330805		paronmanukyan	Poklon (COCI17_poklon)	C++20	140 / 140	574 ms	14916 KiB

poklon

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define ll long long
#define V vector
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr);

struct Query {
    int l, r, id;
};

int main() {
    FASTIO

    int n, q;
    cin >> n >> q;

    int sq = max(1, (int)sqrt(n));

    V<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    V<int> comp(a.begin() + 1, a.end());
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());

    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;

    V<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    sort(all(queries), [&](const Query &A, const Query &B) {
        int blockA = (A.l - 1) / sq;
        int blockB = (B.l - 1) / sq;

        if (blockA != blockB)
            return blockA < blockB;

        if (blockA & 1)
            return A.r > B.r;
        return A.r < B.r;
    });

    V<int> cnt(n + 1, 0);
    V<int> ans(q);

    int cur = 0;
    int L = 1, R = 0;

    auto add = [&](int pos) {
        if (cnt[a[pos]] == 2)
            --cur;
        cnt[a[pos]]++;
        if (cnt[a[pos]] == 2)
            ++cur;
    };

    auto remove = [&](int pos) {
        if (cnt[a[pos]] == 2)
            --cur;
        cnt[a[pos]]--;
        if (cnt[a[pos]] == 2)
            ++cur;
    };

    for (auto &qr : queries) {
        while (R < qr.r) add(++R);
        while (R > qr.r) remove(R--);
        while (L < qr.l) remove(L++);
        while (L > qr.l) add(--L);

        ans[qr.id] = cur;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 140 / 140