Submission #954420

#	Time	Username	Problem	Language	Result	Execution time	Memory
954420		amirhoseinfar1385	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	63 ms	10836 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long n;
long long all[maxn];
vector<long long>alls,allv;

void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
}

void pre(){
	alls.resize(n+2);
	allv.resize(n+2);
	for(long long i=1;i<=n;i++){
		allv[i]=all[i];
		while((allv[i]&1)==0){
			allv[i]>>=1;
		}
		alls[i+1]=alls[i]+all[i]/allv[i];
	}
}

void solve(){
	long long q;
	cin>>q;
	for(long long i=0;i<q;i++){
		long long x;
		cin>>x;
		long long p=lower_bound(alls.begin(),alls.end(),x)-alls.begin();
		p--;
		cout<<allv[p]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40