oj.uz

Submission #942066

# Submission time Handle Problem Language Result Execution time Memory
942066 2024-03-10T07:46:26 Z Alexabcde1 Intercastellar (JOI22_ho_t1) C++14
100 / 100
 276 ms 11132 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
long long n,i,j,si[200005],cnt[200005],q,tmp;
long long a[200005];
long long f(long long x){
	if (x==1) return si[1];
	long long l=1; long long r=n;
	long long ans=0;
	while (l<=r){
		long long mid=(l+r)/2;
		if (cnt[mid]<x){
			l=mid+1;
		}
		else {
			ans=mid;
			r=mid-1;
		}
	}
	return si[ans];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for (i=1;i<=n;i++) {
		cin>>a[i];
		cnt[i]=1;
		si[i]=a[i];
		while (si[i]%2==0){
			si[i]/=2;
			cnt[i]*=2;
		}
		cnt[i]+=cnt[i-1];
	}
	cin>>q;
	while (q--){
		cin>>tmp;
		cout<<f(tmp)<<endl;
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 55 ms 5724 KB Output is correct
4 Correct 193 ms 5900 KB Output is correct
5 Correct 253 ms 6996 KB Output is correct
6 Correct 127 ms 6160 KB Output is correct
7 Correct 249 ms 7220 KB Output is correct
8 Correct 249 ms 7284 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 2 ms 4444 KB Output is correct
14 Correct 2 ms 4440 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 55 ms 5724 KB Output is correct
4 Correct 193 ms 5900 KB Output is correct
5 Correct 253 ms 6996 KB Output is correct
6 Correct 127 ms 6160 KB Output is correct
7 Correct 249 ms 7220 KB Output is correct
8 Correct 249 ms 7284 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 2 ms 4444 KB Output is correct
21 Correct 2 ms 4444 KB Output is correct
22 Correct 2 ms 4440 KB Output is correct
23 Correct 150 ms 6828 KB Output is correct
24 Correct 113 ms 7252 KB Output is correct
25 Correct 261 ms 10484 KB Output is correct
26 Correct 149 ms 8016 KB Output is correct
27 Correct 122 ms 7504 KB Output is correct
28 Correct 276 ms 10764 KB Output is correct
29 Correct 272 ms 10320 KB Output is correct
30 Correct 194 ms 7552 KB Output is correct
31 Correct 275 ms 11132 KB Output is correct