Submission #1240077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240077		eirinayukari	Poklon (COCI17_poklon)	C++20	140 / 140	495 ms	11148 KiB

poklon

// XD XD
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using ll = long long;
using arr3 = array<int, 3>;

const int MAXN = 5e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;
const int S = 750;

template <typename T>
bool ckmin(T& a, T b) {
    return a > b ? a = b, true : false;
}

template <typename T>
bool ckmax(T& a, T b) {
    return a < b ? a = b, true : false;
}

struct Query {
    int l, r, id;
    bool operator<(const Query& other) const {
        if (l / S != other.l / S) return l < other.l;
        return r < other.r;
    }
};

int n, q;
int a[MAXN];
int cnt[MAXN], uni;
int ans[MAXN];
Query queries[MAXN];

void add(int x) {
    cnt[x]++;
    if (cnt[x] == 2) {
        uni++;
    }

    if (cnt[x] == 3) {
        uni--;
    }
}

void remove(int x) {
    cnt[x]--;
    if (cnt[x] == 2) {
        uni++;
    }

    if (cnt[x] == 1) {
        uni--;
    }
}

void solve(int id) {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    sort(queries + 1, queries + q + 1);

    int l = 1, r = 0;
    uni = 0;
    for (int i = 1; i <= q; i++) {
        while (l > queries[i].l) {
            l--;
            add(a[l]);
        }
        while (r < queries[i].r) {
            r++;
            add(a[r]);
        }
        while (l < queries[i].l) {
            remove(a[l]);
            l++;
        }
        while (r > queries[i].r) {
            remove(a[r]);
            r--;
        }
        ans[queries[i].id] = uni;
    }

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

• Subtask 1: 140 / 140