Submission #113881

#	Time	Username	Problem	Language	Result	Execution time	Memory
113881		IVIosab	Poklon (COCI17_poklon)	C++17	140 / 140	1864 ms	46716 KiB

poklon

#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 / 140