Submission #61597191

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 5e5 + 5, inf = 1e18;
int n, q, a[N], b[N], st[20][N];
int query(int l, int r){
  int k = __lg(r - l + 1);
  return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void Solve(){
  cin >> n;
  For(i, 1, n) cin >> a[i];
  int j = n + 1;
  Rof(i, n, 1){
    while(j > i && a[i] * 2 <= a[j - 1]) j--;
    if(j <= n && j != i) b[i] = j; else b[i] = inf;
    st[0][i] = b[i] - i;
  }
  For(i, 1, __lg(n))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 5e5 + 5, inf = 1e18;
int n, q, a[N], b[N], st[20][N];
int query(int l, int r){
	int k = __lg(r - l + 1);
	return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void Solve(){
	cin >> n;
	For(i, 1, n) cin >> a[i];
	int j = n + 1;
	Rof(i, n, 1){
		while(j > i && a[i] * 2 <= a[j - 1]) j--;
		if(j <= n && j != i) b[i] = j; else b[i] = inf;
		st[0][i] = b[i] - i;
	}
	For(i, 1, __lg(n))
		for(int j = 1; j + (1 << i) - 1 <= n; j++)
			st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	//For(i, 1, n) cerr << "b[" << i << "]=" << b[i] << '\n';
	cin >> q;
	while(q--){
		int ql, qr; cin >> ql >> qr;
		int len = qr - ql + 1, l = 1, r = len / 2, pos = 0;
		while(l <= r){
			int mid = (l + r) >> 1;
			//cerr << "mid=" << mid << '\n';
			if(query(ql, ql + mid - 1) <= qr - mid + 1 - ql) l = mid + 1, pos = mid;
			else r = mid - 1;
		}
		cout << pos << '\n';
	}
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int T = 1; //cin >> T;
	while(T--) Solve();
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void Solve()’:
Main.cpp:23:76: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   23 |                         st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
      |                                                                          ~~^~~

Judge Result