Submission #487612

#	Time	Username	Problem	Language	Result	Execution time	Memory
487612		KazamaHoang	Poklon (COCI17_poklon)	C++14	140 / 140	396 ms	42196 KiB

poklon

#include <bits/stdc++.h>

using namespace std;

struct FenwickTree {
    int n;
    vector<int> tree;

    FenwickTree(int _n = 0) {
        n = _n;
        tree.resize(n+5, 0);
    }   

    void update(int x, int sign) {
        for (; x; x -= x & -x)
            tree[x] += sign;
    }

    int get(int x) {
        int res = 0;
        for (; x <= n; x += x & -x)
            res += tree[x];
        return res;
    }
};

int n, q, a[500005];
int last[500005], pre[500005], l[500005], r[500005], ans[500005];
vector<int> qry[500005];

void compress() {
    vector<int> vt(a + 1, a + 1 + n);
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    for (int i = 1; i <= n; ++ i) 
        a[i] = upper_bound(vt.begin(), vt.end(), a[i]) - vt.begin();
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    compress();
    FenwickTree ft(n);
    for (int i = 1; i <= q; ++ i) {
        cin >> l[i] >> r[i];
        qry[r[i]].push_back(i);
    }
    for (int i = 1; i <= n; ++ i) {
        if (pre[last[a[i]]]) {
            ft.update(pre[last[a[i]]], -1);
            ft.update(pre[pre[last[a[i]]]], 1);
        }
        if (last[a[i]]) {
            ft.update(last[a[i]], 1);
            ft.update(pre[last[a[i]]], -1);
        }
        pre[i] = last[a[i]];
        last[a[i]] = i; 
        for (int& id : qry[i]) 
            ans[id] = ft.get(l[id]);
    }
    for (int i = 1; i <= q; ++ i)
        cout << ans[i] << "\n"; 
    return 0;
}

• Subtask 1: 140 / 140