4-й этап Республиканской олимпиады по информатике 2022-2023, 2-й тур

Задача D. Массив и запросы

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

Абай принес вам простую задачу без легенды. Задан массив $A$, состоящий из $N$ натуральных чисел, а также $Q$ запросов вида $L, R$. Ответом на запрос является максимальное целое $K$ ($K \ge 0$), что для него найдется натуральное $X$, при котором числа $X$, $2X$, $4X$, ..., $2^K \cdot X$ встречаются среди чисел $A_L$, $A_{L+1}$, ..., $A_R$. Ваша задача -- посчитать ответ на каждый запрос. Примечание: натуральным называется целое число больше нуля.

Формат входного файла

В первой строке выходных данных заданы два натуральных числа $N$ и $Q$ ($1 <= N, Q <= 5 \cdot 10^5$). Во второй строке задается массив $A$ ($1 <= A_i <= 10^{18}$). Начиная с третьей строки, задаются запросы $L$, $R$ ($1 <= L <= R <= N$). Каждый запрос задан в отдельной строке.

Формат выходного файла

Выведите $Q$ строк, в $i$-й строке должен быть ответ на $i$-й запрос.

Пример:

Вход

6 3
6 9 12 24 18 9
2 3
4 6
1 5

Ответ

0
1
2

Замечание

Пояснение к примеру: В во втором запросе можно выбрать 18 и 9, тогда $K = 1, X = 9$. В третьем запросе -- 6, 12 и 24 ($K = 2, X = 6$). ( Abay Baimukanov )

Комментарий/решение

#include <bits/stdc++.h>

using namespace std;

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back

#define ll long long

#define s second

#define f first

//#define sz(v) int(v.size())

#define all(v) v.begin(),v.end()

int mod = 1e9 + 7;

const int N = 5e5 + 10;

const ll inf = 1e18,k = 61;

unordered_map <ll,int> mp;

int dp[N][k + 3];

void solve(){

int n,q;

cin >> n >> q;

ll a[n + 1];

for(int i = 1; i <= n; i++){

cin >> a[i];

}

for(int i = 1; i <= n; i++){

ll x = a[i] / 2,y = a[i] * 2,cnt = 1;

if(x * 2 != a[i]) x = -1;

dp[i][1] = i;

while(cnt < k){

if(mp.count(x) && (!mp.count(y) || mp[x] >= mp[y])){

cnt++;

dp[i][cnt] = min(mp[x],dp[i][cnt - 1]);

if(x & 1) x = -1;

else x /= 2;

}

else if(mp.count(y) && (!mp.count(x) || mp[x] < mp[y])){

cnt++;

dp[i][cnt] = min(mp[y],dp[i][cnt - 1]);

y *= 2;

}

else break;$$

}

for(int j = 1; j <= k; j++){

dp[i][j] = max(dp[i - 1][j],dp[i][j]);

}

mp[a[i]] = i;

}

while(q--){

int l,r;

cin >> l >> r;

int ans = 1;

for(int i = 1; i <= k; i++){

if(dp[r][i] < l) break;

ans = i;

}

cout << ans - 1 << '\n';

}

}

signed main(){

//freopen("closing.in", "r", stdin);

//freopen("closing.out", "w", stdout);

ios_base::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

int t1 = 1;

while(t1--){

solve();

}

}