oj.uz

Submission #1107849

# Submission time Handle Problem Language Result Execution time Memory
1107849 2024-11-02T08:08:45 Z mychecksedad Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 94112 KB 
/* 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 53840 KB Output is correct
2 Correct 13 ms 53840 KB Output is correct
3 Correct 13 ms 53840 KB Output is correct
4 Correct 11 ms 53840 KB Output is correct
5 Correct 12 ms 53840 KB Output is correct
6 Correct 12 ms 54008 KB Output is correct
7 Correct 11 ms 53840 KB Output is correct
8 Correct 15 ms 53840 KB Output is correct
9 Correct 11 ms 53840 KB Output is correct
10 Correct 10 ms 53944 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 53840 KB Output is correct
2 Correct 13 ms 53840 KB Output is correct
3 Correct 13 ms 53840 KB Output is correct
4 Correct 11 ms 53840 KB Output is correct
5 Correct 12 ms 53840 KB Output is correct
6 Correct 12 ms 54008 KB Output is correct
7 Correct 11 ms 53840 KB Output is correct
8 Correct 15 ms 53840 KB Output is correct
9 Correct 11 ms 53840 KB Output is correct
10 Correct 10 ms 53944 KB Output is correct
11 Execution timed out 4075 ms 54628 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 94020 KB Output is correct
2 Correct 78 ms 93984 KB Output is correct
3 Correct 75 ms 94028 KB Output is correct
4 Correct 109 ms 94024 KB Output is correct
5 Correct 107 ms 94024 KB Output is correct
6 Incorrect 93 ms 94112 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 53840 KB Output is correct
2 Correct 13 ms 53840 KB Output is correct
3 Correct 13 ms 53840 KB Output is correct
4 Correct 11 ms 53840 KB Output is correct
5 Correct 12 ms 53840 KB Output is correct
6 Correct 12 ms 54008 KB Output is correct
7 Correct 11 ms 53840 KB Output is correct
8 Correct 15 ms 53840 KB Output is correct
9 Correct 11 ms 53840 KB Output is correct
10 Correct 10 ms 53944 KB Output is correct
11 Execution timed out 4075 ms 54628 KB Time limit exceeded
12 Halted 0 ms 0 KB -