제출 #1166421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166421		sunflower	Poklon (COCI17_poklon)	C++17	140 / 140	566 ms	15048 KiB

poklon

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int n, q;

#define MAX_N 500'500
int a[MAX_N + 2], cnt[MAX_N + 2], res[MAX_N + 2];

int POS(int x, const vector <int> &v) {
    return lower_bound(ALL(v), x) - v.begin() + 1;
}

const int BLOCK = 707;

int getblock(int x) {
    return (x + BLOCK - 1) / BLOCK;
}

#define MAX_QUERY 500'500
struct Query {
    int l, r, id;

    bool operator < (const Query &other) const {
        if (getblock(l) != getblock(other.l)) return (l < other.l);
        return (r < other.r);
    }
} query[MAX_QUERY + 2];

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n >> q;
    vector <int> v;
    FOR(i, 1, n) cin >> a[i], v.push_back(a[i]);
    sort(ALL(v));
    v.erase(unique(ALL(v)), v.end());

    FOR(i, 1, n) a[i] = POS(a[i], v);

    FOR(i, 1, q) cin >> query[i].l >> query[i].r, query[i].id = i;

    sort(query + 1, query + 1 + q);

    memset(cnt, 0, sizeof(cnt));

    int L = query[1].l, R = query[1].r;
    int ans = 0;
    FOR(i, L, R) {
        cnt[a[i]]++;
        if (cnt[a[i]] == 2) ++ans;
        else if (cnt[a[i]] == 3) --ans;
    }

    res[query[1].id] = ans;

    FOR(i, 2, q) {
        while (L < query[i].l) {
            cnt[a[L]]--;
            if (cnt[a[L]] == 2) ++ans;
            if (cnt[a[L]] == 1) --ans;

            ++L;
        }

        while (L > query[i].l) {
            --L;
            cnt[a[L]]++;
            if (cnt[a[L]] == 2) ++ans;
            if (cnt[a[L]] == 3) --ans;
        }

        while (R > query[i].r) {
            cnt[a[R]]--;
            if (cnt[a[R]] == 2) ++ans;
            if (cnt[a[R]] == 1) --ans;

            --R;
        }

        while (R < query[i].r) {
            ++R;
            cnt[a[R]]++;
            if (cnt[a[R]] == 2) ++ans;
            if (cnt[a[R]] == 3) --ans;
        }

        res[query[i].id] = ans;
    }

    FOR(i, 1, q) cout << res[i] << "\n";

    return 0;
}

/* Discipline - Calm */

• Subtask 1: 140 / 140