Submission #1124412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124412		GasmaskChan	Poklon (COCI17_poklon)	C++17	140 / 140	434 ms	45756 KiB

poklon

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAX = 5e5 + 5;

struct wifi {
    int n;
    vector<int> BIT;

    wifi(int n) : n(n) {
        BIT.assign(n + 5, 0);
    }

    void update(int i, const int &val) {
        for (; i <= n; i += -i & i) BIT[i] += val;
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= -i & i) res += BIT[i];
        return res;
    }
};

vector<int> nen;
int a[MAX], ans[MAX], pre[MAX], posi[MAX];
vector<pair<int, int>> query[MAX];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("btd.inp", "r", stdin); freopen("btd.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        nen.push_back(a[i]);
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        query[r].emplace_back(l, i);
    }

    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());

    wifi waifu(n);
    for (int r = 1;  r <= n; r++) {
        a[r] = lower_bound(nen.begin(), nen.end(), a[r]) - nen.begin() + 1;
        if (posi[a[r]]) {
            pre[r] = posi[a[r]];
            waifu.update(pre[r], 1);
            if (pre[pre[r]]) waifu.update(pre[pre[r]], -2);
            if (pre[pre[pre[r]]]) waifu.update(pre[pre[pre[r]]], 1);
        }
        posi[a[r]] = r;

        for (auto &cur : query[r]) {
            int l, id;
            tie(l, id) = cur;
            ans[id] = waifu.get(r) - waifu.get(l - 1);
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

• Subtask 1: 140 / 140