Submission #1131771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131771		giorgi123glm	Poklon (COCI17_poklon)	C++20	140 / 140	1414 ms	95248 KiB

poklon

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <deque>
using namespace std;

int n = 0, q = 0, siz = 1;
vector <int> v;
map <pair <int, int>, int> ans;
map <int, vector <int> > queries;
vector <pair <int, int> > queries1;
map <int, deque <int> > inds;
vector <int> segtree;
vector <int> lazytree;

void apply_lazy (int u, int l, int r) {
    segtree[u] += lazytree[u];

    if (l != r) {
        lazytree[2 * u] += lazytree[u];
        lazytree[2 * u + 1] += lazytree[u];
    }

    lazytree[u] = 0;
}

void update_segtree (int L, int R, int K, int u, int l, int r) {
    apply_lazy (u, l, r);
    
    if (r < L || R < l)
        return;

    if (L <= l && r <= R) {
        lazytree[u] = K;
        apply_lazy (u, l, r);
        return;
    }

    const int m = (l + r) / 2;
    update_segtree (L, R, K, 2 * u, l, m);
    update_segtree (L, R, K, 2 * u + 1, m + 1, r);
}

int get_segtree (int L, int R, int u, int l, int r) {
    apply_lazy (u, l, r);

    if (r < L || R < l)
        return 0;

    if (L <= l && r <= R)
        return segtree[u];

    const int m = (l + r) / 2;
    return (
        get_segtree (L, R, 2 * u, l, m) +
        get_segtree (L, R, 2 * u + 1, m + 1, r)
    );
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    cin >> n >> q;

    while (siz < n)
        siz *= 2;

    segtree.resize (2 * siz);
    lazytree.resize (2 * siz);
    v.resize (n + 1);

    for (int i = 1; i <= n; i++)
        cin >> v[i];
    for (int i = 1; i <= q; i++) {
        int l = 0, r = 0;
        cin >> l >> r;

        queries[r].emplace_back (l);
        queries1.emplace_back (l, r);
    }

    for (int i = 1; i <= n; i++) {
        deque <int>& deq = inds[v[i]];
        deq.emplace_back (i);
        if (deq.size() == 2)
            update_segtree (1, deq[0], 1, 1, 1, siz);
        else if (deq.size() == 3) {
            update_segtree (1, deq[0], -1, 1, 1, siz);
            update_segtree (deq[0] + 1, deq[1], 1, 1, 1, siz);
        } else if (deq.size() == 4) {
            update_segtree (deq[0] + 1, deq[1], -1, 1, 1, siz);
            update_segtree (deq[1] + 1, deq[2], 1, 1, 1, siz);
            deq.pop_front ();
        }

        for (int& e : queries[i])
            ans[{e, i}] = get_segtree (e, e, 1, 1, siz);
    }

    for (pair <int, int>& e : queries1)
        cout << ans[e] << '\n';
}

• Subtask 1: 140 / 140