Submission #734493

#	Time	Username	Problem	Language	Result	Execution time	Memory
734493		1075508020060209tc	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	441 ms	10820 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
int inf=1e15;
int n;int Q;
int oar[200005];
int ar[200005];
int ps[200005];

signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    cin>>oar[i];
    ps[i]=ps[i-1];
    int v=oar[i];int cnt=0;
    while(v%2==0){
        cnt++;v/=2;
    }
    ar[i]=(1ll<<(cnt));
    if(ps[i-1]>=1e15){continue;}
    ps[i]=ar[i]+ps[i-1];
}
/*
for(int i=1;i<=n;i++){
    cout<<ps[i]<<" ";
}cout<<endl;
*/
cin>>Q;
while(Q--){
    int pl;
    cin>>pl;
    int l=1;int r=n;
    while(l<r){
        int mi=l+(r-l)/2;
        if(ps[mi]>=pl){
            r=mi;
        }else{
            l=mi+1;
        }
    }
    int v=oar[l];
    while(v%2==0){
        v/=2;
    }
    cout<<v<<endl;
}

}

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