Submission #1305089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305089		muhammad-ahmad	Index (COCI21_index)	C++20	60 / 110	1522 ms	589824 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, sq, a[N];
int block[400][N] = {};

int sum(int L, int R, int x) {
	int ans = 0;
	while (L <= R && L % sq != 1) {
		if (a[L] >= x) ans++;
		L++;
	}
	while (L <= R && R % sq != 0) {
		if (a[R] >= x) ans++;
		R--;
	}
	while (L <= R) {
		int b = (L + sq - 1) / sq;
		ans += block[b][x];
		L += sq;
	}
	return ans;
}

void solve() {
	cin >> n >> q;
	sq = sqrt(n) + 1;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	
	for (int i = 1; i <= n; i += sq){
		for (int j = i; j <= min(n, i + sq - 1); j++){
			block[(i + sq - 1) / sq][a[j]]++;
		}
		for (int j = N - 2; j >= 0; j--){
			block[(i + sq - 1) / sq][j] += block[(i + sq - 1) / sq][j + 1];
		}
	}
	
	for (int Q = 1; Q <= q; Q++){
		int L, R; cin >> L >> R;
		int l = 0, r = N;
		while (r - l > 1){
			int mid = (l + r) / 2;
			int val = sum(L, R, mid);
			if (val >= mid) l = mid;
			else r = mid;
		}
		cout << l << 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: 0 / 50