Submission #760190

#	Time	Username	Problem	Language	Result	Execution time	Memory
760190		Petrix	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	377 ms	10728 KiB

Main

#include <iostream>
using namespace std;

struct sirNou{
    long long s,e,val;
} v[200001];

void gasesteVal(long long a,long long i){
    long long put=1;
    while(a%2==0){
        put*=2;
        a/=2;
    }
    v[i].s=v[i-1].e+1;
    v[i].e=v[i-1].e+put;
    v[i].val=a;
}

int main()
{
    long long n,i,q,st,dr,mij,a,gas;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a;
        if(a%2==1){
            v[i].val=a;
            v[i].s=v[i].e=v[i-1].e+1;
        }else{
            gasesteVal(a,i);
        }
    }
    cin>>q;
    for(i=0;i<q;i++){
        cin>>gas;
        st=1;dr=n;
        while(st<=dr){
            mij=(st+dr)/2;
            if(v[mij].s<=gas && v[mij].e>=gas){
                cout<<v[mij].val<<"\n";
                break;
            }else if(v[mij].s>gas){
                dr=mij-1;
            }else{
                st=mij+1;
            }
        }


    }
    return 0;
}

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