Submission #923479

#	Time	Username	Problem	Language	Result	Execution time	Memory
923479		Isam	Index (COCI21_index)	C++17	20 / 110	2532 ms	2128 KiB

index

#include<bits/stdc++.h>

using namespace std;

constexpr int sz = 50001;

int n, Q, c[sz], ans[sz];

struct que{
	int index, l, r;
} q[sz];


bool cmp(que a, que b){
	if(a.r ^ b.r) return a.r < b.r;
	return a.l < b.l;
}

bool check(int mid, int l, int r){
	int cur(0);
	for(register int i = l; i <= r; ++i){
		cur += (c[i] >= mid);
	}
	return cur >= mid;
}

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> Q;
	for(register int i = 1; i <= n; ++i){
		cin >> c[i];
	}
	for(register int i = 1; i <= Q; ++i){
		cin >> q[i].l >> q[i].r, q[i].index = i;
	}
	
	sort(q+1, q+Q+1, cmp);
	
	
	
	int i(1), l, r;
	
	while(i <= n){
		l = q[i].l, r = q[i].r;
		int L(1), R(r - l + 1), mid, best(1);
		while(L <= R){
			mid = L + ((R - L) >> 1);
			if(check(mid, l, r)){
				best = mid;
				L = mid + 1;
			}else{
				R = mid - 1;
			}
		}
		ans[q[i].index] = best;
		++i;
	}
	
	for(register int i = 1; i <= Q; ++i){
		cout << ans[i] << '\n';
	}
	
	
	return 0;	
}
/*
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7


*/

Compilation message (stderr)

index.cpp: In function 'bool check(int, int, int)':
index.cpp:21:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   21 |  for(register int i = l; i <= r; ++i){
      |                   ^
index.cpp: In function 'int main()':
index.cpp:30:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   30 |  for(register int i = 1; i <= n; ++i){
      |                   ^
index.cpp:33:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   33 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:59:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   59 |  for(register int i = 1; i <= Q; ++i){
      |                   ^

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