Submission #113880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
113880	2019-05-29T02:19:27 Z	IVIosab	Poklon (COCI17_poklon)	C++17	140 / 140	2492 ms	57200 KB

poklon

#include <bits/stdc++.h>

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

void update(int x, int u, int s, int e, int p) {
    if (s > u || e < u) {
        return;
    }
    if (s == e) {
        tree[p] += x;
        return;
    }

    int mid = s + (e - s) / 2;
    update(x, u, s, mid, p * 2 + 1);
    update(x, u, mid + 1, e, p * 2 + 2);
    tree[p] = tree[p * 2 + 1] + tree[p * 2 + 2];
}

int query(int qs, int qe, int ns, int ne, int ind) {
    if (ns > qe || ne < qs) {
        return 0;
    }
    if (ns >= qs && ne <= qe) {
        return tree[ind];
    }
    int mid = ns + (ne - ns) / 2;
    return query(qs, qe, ns, mid, ind * 2 + 1) + query(qs, qe, mid + 1, ne, ind * 2 + 2);
}

void print(){
    for(int i=0; i<n; i++)
        cout << query(i, i, 0, n-1, 0) << " ";
    cout << endl;
}
void printadd(int v, int x){
    cout << "adding : " << v << " at " << x << endl;
}
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) {
            //update(-1, lef[lef[i]]+1, 0, n - 1, 0);
            update(1, lef[i], 0, n - 1, 0);
            //printadd(1, lef[i]);
        } else if (cnt[ar[i]] > 2) {
            if (cnt[ar[i]] > 3) {
                update(1, lef[lef[lef[i]]], 0, n - 1, 0);
                //printadd(1, lef[lef[lef[i]]]);
            }
            update(-1, lef[lef[i]], 0, n - 1, 0);
            //printadd(-1, lef[lef[i]]);

            update(-1, lef[lef[i]], 0, n - 1, 0);
            //printadd(-1, lef[lef[i]]);

            update(1, lef[i], 0, n - 1, 0);
            //printadd(1, lef[i]);
        }
        while (pr[qind].first == i) {
            res[pr[qind]] = query(pr[qind].second, pr[qind].first, 0, n - 1, 0);
            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	384 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	16 ms	948 KB	Output is correct
5	Correct	382 ms	11656 KB	Output is correct
6	Correct	380 ms	11896 KB	Output is correct
7	Correct	879 ms	23412 KB	Output is correct
8	Correct	1407 ms	36216 KB	Output is correct
9	Correct	1890 ms	46584 KB	Output is correct
10	Correct	2492 ms	57200 KB	Output is correct