oj.uz

Submission #487612

# Submission time Handle Problem Language Result Execution time Memory
487612 2021-11-16T09:34:58 Z KazamaHoang Poklon (COCI17_poklon) C++14
140 / 140
 396 ms 42196 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12112 KB Output is correct
2 Correct 7 ms 12112 KB Output is correct
3 Correct 7 ms 12112 KB Output is correct
4 Correct 9 ms 12368 KB Output is correct
5 Correct 61 ms 17844 KB Output is correct
6 Correct 61 ms 17880 KB Output is correct
7 Correct 142 ms 23924 KB Output is correct
8 Correct 231 ms 30116 KB Output is correct
9 Correct 306 ms 36268 KB Output is correct
10 Correct 396 ms 42196 KB Output is correct