Submission #1189681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189681		gustavo_d	Index (COCI21_index)	C++20	110 / 110	239 ms	52856 KiB

index

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

const int MAXN = 200001;
const int MAXNODES = MAXN * 200;

int val[MAXN];

struct Node {
	int sum;
	Node(int _sum=0): sum(_sum) {}
	Node operator+(Node right) {
		Node left = *this;
		return Node(left.sum + right.sum);
	}
};

struct SEG {
	int n; vector<Node> seg; vector<int> ls, rs;

	SEG(int _n=0) {
		n = 1;
		while (n < _n) n <<= 1;

		seg.reserve(MAXNODES);
		ls.reserve(MAXNODES);
		rs.reserve(MAXNODES);

		createNode();
		createNode();
	}

	int createNode(int src = 0) {
		seg.push_back(src == 0 ? Node() : seg[src]);
		ls.push_back(src == 0 ? 0 : ls[src]);
		rs.push_back(src == 0 ? 0 : rs[src]);
		return (int)seg.size() - 1;
	}

	int getLeft(int v) {
		return ls[v] = (ls[v] == 0 ? createNode() : ls[v]);
	}

	int getRight(int v) {
		return rs[v] = (rs[v] == 0 ? createNode() : rs[v]);
	}

	int add(int v, int l, int r, int i, int x) {
		v = createNode(v);
		if (l == r) {
			seg[v].sum += x;
			return v;
		}
		int m = (l + r) / 2;
		if (i <= m) ls[v] = add(getLeft(v), l, m, i, x);
		else rs[v] = add(getRight(v), m+1, r, i, x);
		seg[v] = seg[getLeft(v)] + seg[getRight(v)];
		return v;
	}

	int findH(int vl, int vr, int l, int r, int bigger) {
		if (l == r) return l;
		int m = (l + r) / 2;
		int right = seg[getRight(vr)].sum - seg[getRight(vl)].sum;
		// cout << l << ' ' << r << ' ' << bigger << ' ' << right << endl;
		if (m+1 <= bigger + right)
			return findH(getRight(vl), getRight(vr), m+1, r, bigger);
		else return findH(getLeft(vl), getLeft(vr), l, m, bigger + right);
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n, qs; cin >> n >> qs;
	for (int i=1; i<=n; i++) cin >> val[i];
	
	SEG seg(MAXN);
	vector<int> versions{1};
	for (int i=1; i<=n; i++) {
		versions.push_back(seg.add(versions.back(), 0, seg.n-1, val[i], 1));
	}

	for (int q=0; q<qs; q++) {
		int l, r; cin >> l >> r;
		cout << seg.findH(versions[l-1], versions[r], 0, seg.n-1, 0) << '\n';
	}

	return 0;
}

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