Submission #751864

#	Time	Username	Problem	Language	Result	Execution time	Memory
751864		HoriaHaivas	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	103 ms	13820 KiB

Main

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct interval
{
    int l;
    int r;
    int val;
};

int desc(int x)
{
    while (x%2==0)
    {
        x=x/2;
    }
    return x;
}

int lungime(int x)
{
    int l=1;
    while (x%2==0)
    {
        x=x/2;
        l=l*2;
    }
    return l;
}

int v[200001];
interval span[200001];
int sp[200001];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n,i,j,q,cnt,x,r,pas;
    cin >> n;
    for (i=1;i<=n;i++)
    {
         cin >> v[i];
    }
    cnt=0;
    for (i=1;i<=n;i++)
    {
         cnt++;
         span[cnt].val=desc(v[i]);
         span[cnt].l=span[cnt-1].r+1;
         span[cnt].r=span[cnt].l+lungime(v[i])-1;
    }
    for (i=1;i<=cnt;i++)
    {
         sp[i]=sp[i-1]+span[i].r-span[i].l+1;
    }
    cin >> q;
    for (i=1;i<=q;i++)
    {
         cin >> x;
         r=0;
         pas=(1<<17);
         while (pas)
         {
              if (r+pas<=cnt && sp[r+pas]<x)
                  r+=pas;
              pas=pas/2;
         }
         cout << span[r+1].val << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:49:19: warning: unused variable 'j' [-Wunused-variable]
   49 |     long long n,i,j,q,cnt,x,r,pas;
      |                   ^

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