Submission #851326

#	Time	Username	Problem	Language	Result	Execution time	Memory
851326		serifefedartar	Index (COCI21_index)	C++17	110 / 110	361 ms	9976 KiB

index

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;

const ll SQ = 500;
vector<pair<pair<int,int>,int>> query;
vector<int> A;
int ans[MAXN], suff[MAXN], res = 1, cnt = 1;
void insert(int x) {
	suff[A[x]]++;
	if (A[x] >= res)
		cnt++;

	if (cnt - suff[res] > res) {
		cnt -= suff[res];
		res++;
	}
}

void omit(int x) {
	suff[A[x]]--;
	if (A[x] >= res)
		cnt--;

	if (cnt < res) {
		res--;
		cnt += suff[res];
	}
}

int main() {
	fast
	int N, Q;
	cin >> N >> Q;

	A = vector<int>(N+1);
	query = vector<pair<pair<int,int>,int>>(Q);
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	for (int i = 0; i < Q; i++) {
		cin >> query[i].f.f >> query[i].f.s;
		query[i].s = i;
	}
	sort(query.begin(), query.end(), [&](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
		return make_pair(a.f.f / SQ, a.f.s) < make_pair(b.f.f / SQ, b.f.s);
	});

	int l = 1, r = 1;
	suff[A[1]]++;
	for (auto u : query) {
		int new_l = u.f.f;
		int new_r = u.f.s;
		while (new_l < l) {
			l--;
			insert(l);
		}
		
		while (new_r > r) {
			r++;
			insert(r);
		}
		
		while (new_l > l) {
			omit(l);
			l++;
		}
		
		while (new_r < r) {
			omit(r);
			r--;
		}

		ans[u.s] = res;
	}

	for (int i = 0; i < Q; i++)
		cout << ans[i] << "\n";
}

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