Submission #798306

#	Time	Username	Problem	Language	Result	Execution time	Memory
798306		n3rm1n	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	89 ms	12316 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, q;
long long a[MAXN];
long long r[MAXN], cnt[MAXN], pref[MAXN];
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        r[i] = a[i];
        while(r[i] % (1LL * 2) == 0)
            r[i] /= (1LL * 2);
        cnt[i] = a[i] / r[i];
        pref[i] = pref[i-1] + cnt[i];
    }
   // for (int i = 1; i <= n; ++ i)
       // cout << r[i] << " " << cnt[i] << " " << pref[i] << endl;
}

long long x;
void solve_query()
{
    int left = 0, right = n, mid, ans = 0;
    while(left <= right)
    {
        mid = (left + right)/2;
        if(pref[mid] < x)
        {
            ans = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    ans ++;
    cout << r[ans] << endl;
}
void queries()
{
    cin >> q;
    while(q --)
    {
        cin >> x;
        solve_query();
    }
}
int main()
{
    speed();

    read();
    queries();
    return 0;
}

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