Submission #1221788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221788		sula2	Index (COCI21_index)	C++20	0 / 110	1 ms	576 KiB

index

#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;

struct node {
    long long sum = 0;
    node *l = nullptr, *r = nullptr;
    int L, R;

    node(int L, int R) : L(L), R(R) {}

    node* update(int ind, int x) {
        if (R - L == 1) {
            node* new_node = new node(L, R);
            new_node->sum = sum + x;
            return new_node;
        }
        node* new_node = new node(L, R);
        int mid = (L+R)/2;
        if (l == nullptr) l = new node(L, mid);
        if (r == nullptr) r = new node(mid, R);
        new_node->l = l;
        new_node->r = r;
        if (ind < mid) {
            new_node->l = l->update(ind, x);
        } else {
            new_node->r = r->update(ind, x);
        }
        new_node->sum = new_node->l->sum + new_node->r->sum;
        return new_node;
    }

    long long query(int ql, int qr) {
        if (ql <= L && R <= qr) {
            return sum;
        }
        if (qr <= L || R <= ql) return 0;
        return (l == nullptr ? 0 : l->query(ql, qr))
            +  (r == nullptr ? 0 : r->query(ql, qr));
    }

    void dfs() {
        cout << L << " " << R << " " << sum << '\n';
        if (l != nullptr)
            l->dfs();
        if (r != nullptr)
            r->dfs();
    }
};

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

    const int A = 16;
    int n,q; cin >> n >> q;
    vector<node*> roots { new node(0, A) };
    for (int i = 0; i < n; i++) {
        int ai; cin >> ai;
        roots.push_back(roots.back());
        roots.back() = roots.back()->update(ai, 1);
    }
    while (q--) {
        int l,r; cin >> l >> r;
        l--;

        auto root_l = roots[l];
        auto root_r = roots[r];
        int sum = 0;
        while (root_l->l != nullptr) {
            assert(root_l ->L == root_r ->L);
            assert(root_l ->R == root_r ->R);

            int x = sum + root_r -> r -> sum - root_l -> r -> sum;
            int mid = (root_r -> L + root_r -> R)/2;
            if (mid <= x) {
                root_r = root_r->r;
                root_l = root_l->r;
            } else {
                root_r = root_r->l;
                root_l = root_l->l;
                sum += x;
            }
        }
        cout << root_r -> L << "\n";
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50