oj.uz

Submission #113881

# Submission time Handle Problem Language Result Execution time Memory
113881 2019-05-29T02:37:57 Z IVIosab Poklon (COCI17_poklon) C++17
140 / 140
 1864 ms 46716 KB 
#include <bits/stdc++.h>

using namespace std;
//#define f first
//#define s second
#define ll long long
const int N = 500005;
pair<int, int> pr[N], in[N];
int n, q;
int ar[N];
int lef[N];

struct BIT {
    int tree[2 * N];

    int get_sum(int x) {
        ++x;
        int sum = 0;
        for (int i = x; i; i -= i & (-i)) {
            sum += tree[i - 1];
        }
        return sum;
    }

    void update(int x, int v) {
        ++x;
        for (int i = x; i <= N; i += i & (-i)) {
            tree[i - 1] += v;
        }
    }

    int lower_bound(int val) { // returns first index with cummulative greatrer than or equal val
        int st = 0;
        for (int sz = N >> 1; sz; sz >>= 1)
            if (val > tree[st + sz - 1])
                val -= tree[(st += sz) - 1];
        return st;
    }
} bit;


int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> ar[i];
        auto it = mp.find(ar[i]);
        if (it == mp.end()) {
            lef[i] = -1;
        } else {
            lef[i] = mp[ar[i]];
        }
        mp[ar[i]] = i;
    }

    for (int i = 0; i < q; i++) {
        cin >> pr[i].second >> pr[i].first; //first=Right, second=Left;
        in[i].first = --pr[i].first;
        in[i].second = --pr[i].second;
    }

    sort(pr, pr + q);
    int qind = 0;
    map<int, int> cnt;
    map<pair<int, int>, int> res;

    for (int i = 0; i < n; i++) {
        cnt[ar[i]]++;
        if (cnt[ar[i]] == 2) {
            bit.update(0, 1);
            bit.update(lef[i]+1, -1);
        } else if (cnt[ar[i]] > 2) {
            bit.update(lef[lef[lef[i]]] + 1, -1);
            bit.update(lef[lef[i]] + 1, +1);

            bit.update(lef[lef[i]] + 1, 1);
            bit.update(lef[i] + 1, -1);
        }
        while (pr[qind].first == i) {
            res[pr[qind]] = bit.get_sum(pr[qind].second);
            qind++;
        }
        //cout << i<< " : " << endl;
        //print();
    }
    for (int i = 0; i < q; i++) {
        cout << res[in[i]] << endl;
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 13 ms 896 KB Output is correct
5 Correct 299 ms 9804 KB Output is correct
6 Correct 296 ms 9780 KB Output is correct
7 Correct 701 ms 19064 KB Output is correct
8 Correct 1086 ms 28368 KB Output is correct
9 Correct 1454 ms 37424 KB Output is correct
10 Correct 1864 ms 46716 KB Output is correct