Submission #538032

#	Time	Username	Problem	Language	Result	Execution time	Memory
538032		ddy888	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	99 ms	6964 KiB

Main

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

int N, Q, A[200010];

signed main() {
    fast;
    cin >> N;
    vector<int> cnt(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        int x = A[i];
        while (x % 2 == 0) x /= 2;
        cnt[i] = A[i] / x;
    }
    for (int i = 1; i <= N; ++i) cnt[i] += cnt[i - 1];
    cin >> Q;
    while (Q--) {
        int pos; cin >> pos;
        auto it = lower_bound(cnt.begin(), cnt.end(), pos);
        if (it == cnt.end()) {
            cout << 0 << '\n';
            continue;
        }
        int ans = A[it - cnt.begin()];
        while (ans % 2 == 0) ans /= 2;
        cout << ans << '\n';
    }
    return 0;
}

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