Submission #1107849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107849		mychecksedad	Triple Jump (JOI19_jumps)	C++17	5 / 100	4075 ms	94112 KiB

jumps

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 20, MX = 1000;


int n, a[N], rmq[N][K], LOG2[N];
vector<int> T[N*2];
int mn(int l, int r){
	if(l > r) return -MOD;
	int k = LOG2[r-l+1];
	return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
void build(int l, int r, int k){
	if(l == r){
		T[k].pb(l);
		return;
	}
	int m = l+r>>1;
	build(l, m, k<<1);
	build(m+1, r, k<<1|1);
	merge(all(T[k<<1]), all(T[k<<1|1]), back_inserter(T[k]), [&](const int &x, const int &y){
		return a[x] > a[y];
	});
	while(T[k].size() > MX) T[k].pop_back();
}
vi get(int l, int r, int ql, int qr, int k){
	if(l > qr || ql > r) return vi{};
	if(ql <= l && r <= qr) return T[k];
	int m = l+r>>1;
	auto p = get(l, m, ql, qr, k<<1);
	auto p2 = get(m+1, r, ql, qr, k<<1|1);
	vi p3;

	merge(all(p), all(p2), back_inserter(p3), [&](const int &x, const int &y){
		return a[x] > a[y];
	});
	while(p3.size() > MX) p3.pop_back();
	return p3;
}




void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];

  LOG2[1] = 0;
	for(int i = 2; i < N; ++i) LOG2[i] = LOG2[i>>1] + 1;
	
	for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
	for(int j = 1; j < K; ++j){
	    for(int i = 1; i + (1<<j) <= n + 1; ++i){
	        rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
	    }
	}

	build(1, n, 1);
	
//	cout << mn(2, 3) << '\n';

  int q; cin >> q;
	for(int i = 0; i < q; ++i){
		int l, r; cin >> l >> r;
		vi v = get(1, n, l, r, 1);
		int ans = 0;
		const int sz = v.size();
		for(int j = 0; j < sz; j++){
		    //cout << v[j] << ' ';
			for(int k = j + 1; k < sz; ++k){
				int x = v[j], y = v[k];
				if(x>y) swap(x,y);
				ans = max(ans, a[x] + a[y] + 
				    max({
				        mn(max(l, x - (y-x)), x-1), 
				        mn(x + 1, x + (y-x)/2), 
				        mn(min(r+1, y+(y-x)), r)}));
				        //cout << a[x] << ' ' << a[y] << '\n';
				/*if(l==11)
				cout << mn(max(l, x - (y-x)), x-1) << ' ' <<
				        mn(x + 1, min(y-1, x + (y-x)/2)) << ' ' <<
				        mn(min(r+1, y+(y-x)), r) << '\n';
				//cout << x << ' ' << y << ' ' << ans << '\n';
				*/
			}
		}
		cout << ans << '\n';
	}
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    //en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int m = l+r>>1;
      |          ~^~
jumps.cpp: In function 'std::vector<int> get(int, int, int, int, int)':
jumps.cpp:40:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int m = l+r>>1;
      |          ~^~
jumps.cpp: In function 'int main()':
jumps.cpp:105:15: warning: unused variable 'aa' [-Wunused-variable]
  105 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54