oj.uz

Submission #923478

# Submission time Handle Problem Language Result Execution time Memory
923478 2024-02-07T09:49:45 Z Isam Index (COCI21_index) C++17
20 / 110
 6 ms 8284 KB 
#include<bits/stdc++.h>

using namespace std;

constexpr int sz = 1001;

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

int j, tree[sz][sz];

inline void update(int pos, int val){
	while(pos <= n){
		tree[j][pos] += val;
		pos += (pos & (-pos));
	}
	return;
}

int get_ans(int l, int r){
	if(!r || l > r) return 0;
	if(l ^ 1) return get_ans(1, r) - get_ans(1, l - 1);
	int res(0);
	while(r > 0){
		res += tree[j][r];
		r -= (r & (-r));
	}
	return res;
}


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);
	j = r;
	cur += get_ans(mid, n);
	j = l - 1;
	if(j > 0) cur -= get_ans(mid, n);
	
	
	
	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(j = i; j <= n; ++j){
			update(c[i], 1);
		}
	}
	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 'int main()':
index.cpp:56:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   56 |  for(register int i = 1; i <= n; ++i){
      |                   ^
index.cpp:62:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   62 |  for(register int i = 1; i <= Q; ++i){
      |                   ^
index.cpp:91:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   91 |  for(register int i = 1; i <= Q; ++i){
      |                   ^

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4188 KB Output is correct
2 Correct 6 ms 4396 KB Output is correct
3 Correct 5 ms 4188 KB Output is correct
4 Correct 5 ms 4188 KB Output is correct
5 Correct 5 ms 4188 KB Output is correct
6 Correct 5 ms 4188 KB Output is correct
7 Correct 6 ms 4188 KB Output is correct
8 Correct 5 ms 4236 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 6 ms 4188 KB Output is correct
11 Runtime error 4 ms 8284 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4188 KB Output is correct
2 Correct 6 ms 4396 KB Output is correct
3 Correct 5 ms 4188 KB Output is correct
4 Correct 5 ms 4188 KB Output is correct
5 Correct 5 ms 4188 KB Output is correct
6 Correct 5 ms 4188 KB Output is correct
7 Correct 6 ms 4188 KB Output is correct
8 Correct 5 ms 4236 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 6 ms 4188 KB Output is correct
11 Runtime error 4 ms 8284 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -