oj.uz

Submission #923479

# Submission time Handle Problem Language Result Execution time Memory
923479 2024-02-07T09:59:57 Z Isam Index (COCI21_index) C++17
20 / 110
 2500 ms 2128 KB 
#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

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.0 / 20.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 6 ms 356 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 496 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Execution timed out 2532 ms 2128 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 344 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 6 ms 356 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 496 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Execution timed out 2532 ms 2128 KB Time limit exceeded
12 Halted 0 ms 0 KB -