Submission #1124436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124436		votranngocvy	Poklon (COCI17_poklon)	C++20	140 / 140	722 ms	13092 KiB

poklon

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int block_size = 750;
int a[N],ans[N],cnt[N],res;
vector<int>val;

struct Data {
    int l,r,idx;
} query[N];

void add(int x) {
    cnt[x]++;
    if (cnt[x] == 2) res++;
    else if (cnt[x] == 3) res--;
}

void del(int x) {
    cnt[x]--;
    if (cnt[x] == 1) res--;
    else if (cnt[x] == 2) res++;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        val.push_back(a[i]);
    }
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    for (int i = 1; i <= n; i++)
        a[i] = upper_bound(val.begin(),val.end(),a[i]) - val.begin();
    for (int i = 1; i <= q; i++) {
        cin >> query[i].l >> query[i].r;
        query[i].idx = i;
    }
    sort(query + 1,query + q + 1,[&](Data &a,Data &b) {
         if (a.l / block_size == b.l / block_size) return a.r < b.r;
         else return a.l / block_size < b.l / block_size;
    });
    int L = 1,R = 0;
    for (int i = 1; i <= q; i++) {
        int l = query[i].l,r = query[i].r,idx = query[i].idx;
        while (L > l) L--,add(a[L]);
        while (L < l) del(a[L]),L++;
        while (R > r) del(a[R]),R--;
        while (R < r) R++,add(a[R]);
        ans[idx] = res;
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

• Subtask 1: 140 / 140