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

Есеп D. Массив және сұраныстар

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

1.5 seconds

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

256 megabytes

Абай сізге аңызсыз қарапайым есеп әкелді. $N$ натурал саннан тұратын $A$ массиві бар. Оған қоса, $L, R$ түріндегі $Q$ сұраныстары берілген. Сұранысқа жауап — бұл $A_L$, $A_{L+1}$, ..., $A_R$ тізбегінін ішінде, $X$, $2X$, $4X$, ..., $2^K \cdot X$ сандарының бәрі кездесетіндей, $X$ натурал саны табылса, $K$ ($K \ge 0$) санының ең үлкен мәні. Ескерту: натурал сан деп нөлден үлкен бүтін сандарды айтамыз.

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

Бірінші жолда екі $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();

}

}