Submission #1305149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305149		muhammad-ahmad	Index (COCI21_index)	C++20	110 / 110	301 ms	10952 KiB

index

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 2e5 + 5;
int n, q, cur, cur_ans, block, L[N], R[N], ans[N], idx[N], a[N], freq[N];

bool mo_comp (int i, int j){
	int b1 = L[i] / block;
	int b2 = L[j] / block;
	if (b1 != b2) return(b1 < b2);
	return (R[i] < R[j]);
}

void add(int i){
	if (a[i] >= cur_ans) cur++;
	freq[a[i]]++;
	while (cur - freq[cur_ans] > cur_ans){
		cur -= freq[cur_ans];
		cur_ans++;
	}
}

void remove(int i){
	if (a[i] >= cur_ans) cur--;
	freq[a[i]]--;
	while (cur < cur_ans){
		cur_ans--;
		cur += freq[cur_ans];
	}
}

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for (int i = 1; i <= q; i++){
		cin >> L[i] >> R[i];
		idx[i] = i;
	}
	block = sqrt(n) + 1;
	sort(idx + 1, idx + q + 1, mo_comp);
	int Le = 1, Ri = 0;
	for (int i = 1; i <= q; i++){
		int nidx = idx[i];
		int l = L[nidx], r = R[nidx];
		// cout << l << ' ' << r << endl;
		while (Le > l) add(--Le);
		while (Le < l) remove(Le++);
		while (Ri < r) add(++Ri);
		while (Ri > r) remove(Ri--);
		ans[nidx] = cur_ans;
	}
	// cout << Le << ' ' << Ri << endl;
	for (int i = 1; i <= q; i++) cout << ans[i] << endl;
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

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