oj.uz

Submission #923480

# Submission time Handle Problem Language Result Execution time Memory
923480 2024-02-07T10:03:59 Z Isam Index (COCI21_index) C++17
20 / 110
 2500 ms 864 KB 
#include<bits/stdc++.h>

using namespace std;

constexpr int sz = 50001;

int n, Q, c[sz];

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, l, r; i <= Q; ++i){
		cin >> l >> 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;
			}
		}
		cout << best << '\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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 6 ms 472 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 6 ms 472 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 6 ms 472 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 6 ms 472 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Execution timed out 2571 ms 864 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 6 ms 472 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 6 ms 472 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 6 ms 348 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Execution timed out 2571 ms 864 KB Time limit exceeded
12 Halted 0 ms 0 KB -