Submission #1153864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153864		gelastropod	Index (COCI21_index)	C++20	110 / 110	1159 ms	10844 KiB

index

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

int sqrtN;

bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
	if (a.first.first / sqrtN == b.first.first / sqrtN)
		return a.first.second < b.first.second;
	return a.first.first / sqrtN < b.first.first / sqrtN;
}

vector<int> tree;

void upd(int n, int x) {
	while (n < tree.size()) {
		tree[n] += x;
		n += n & (-n);
	}
}

int qry(int a) {
	int ans = 0;
	while (a != 0) {
		ans += tree[a];
		a -= a & (-a);
	}
	return ans;
}

int rqry(int a) {
	if (a <= 0) return 0;
	return qry(tree.size() - 1) - qry(a - 1);
}

signed main() {
	int n, q, p, a, b;
	cin >> n >> q;
	sqrtN = pow(n, 0.5f);
	int numB = (n + sqrtN - 1) / sqrtN;
	vector<int> P;
	vector<pair<pair<int, int>, int>> queries;
	for (int i = 0; i < n; i++) {
		cin >> p;
		P.push_back(p);
	}
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		a--, b--;
		queries.push_back({ { a, b }, i });
	}
	sort(queries.begin(), queries.end(), comp);
	tree = vector<int>(200005, 0);
	int ans = 0;
	vector<int> anss(q, 0);
	pair<int, int> prevquery = { 0, 0 };
	for (int i = 0; i < q; i++) {
		auto query = queries[i];
		int s = query.first.first;
		int e = query.first.second + 1;
		while (prevquery.first < s) {
			upd(P[prevquery.first], -1);
			if (rqry(ans) < ans)
				ans--;
			prevquery.first++;
		}
		while (prevquery.first > s) {
			upd(P[prevquery.first - 1], 1);
			if (rqry(ans + 1) >= ans + 1)
				ans++;
			prevquery.first--;
		}
		while (prevquery.second < e) {
			upd(P[prevquery.second], 1);
			if (rqry(ans + 1) >= ans + 1)
				ans++;
			prevquery.second++;
		}
		while (prevquery.second > e) {
			upd(P[prevquery.second - 1], -1);
			if (rqry(ans) < ans)
				ans--;
			prevquery.second--;
		}
		anss[query.second] = ans;
	}
	for (int i : anss)
		cout << i << '\n';
}

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