Submission #573004

#	Time	Username	Problem	Language	Result	Execution time	Memory
573004		groshi	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	80 ms	11216 KiB

Main

#include<iostream>

using namespace std;
#define int long long
int teraz[300000];
int drzewo[1000000];
int pot=1;
int zap(int x,int co)
{
    if(x>pot)
        return teraz[x-pot];
    if(drzewo[x*2]>=co)
        return zap(x*2,co);
    else return zap(x*2+1,co-drzewo[x*2]);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,x;
    cin>>n;
    while(pot<=n)
        pot*=2;
    pot--;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        int ile=1;
        int pom=x;
        while(pom%2==0)
        {
            ile*=2;
            pom/=2;
        }
        drzewo[i+pot]=ile;
        teraz[i]=x/ile;
    }
    for(int i=pot;i>=1;i--)
        drzewo[i]=drzewo[i*2]+drzewo[i*2+1];
    int zapp;
    cin>>zapp;
    while(zapp--)
    {
        cin>>x;
        cout<<zap(1,x)<<"\n";
    }
    return 0;
}

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