oj.uz

Submission #1020575

# Submission time Handle Problem Language Result Execution time Memory
1020575 2024-07-12T07:08:27 Z vjudge1 Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 18780 KB 
// #pragma once
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e18 + 100;
const int maxn = 1e6 + 100;
const int maxl = 20;

int n, C;
ll a[maxn];
int b[maxn];
ll p[2][maxl][maxn];
int lg[maxn];

ll get(int l, int r, int c){
	if(l > r) return -INF;
	int k = lg[r - l + 1];
	return max(p[c][k][l], p[c][k][r-(1<<k)+1]);
}

ll ans(int l, int r){
	if(l > r) return -INF;
	return get(l, r, 0) + get(l, r, 1);
}

bool ok(ll x){
	int tl = 0, tr = n + 1;
	while(tl < n && ans(1, tl+1) <= x) tl++;
	while(tr > 1 && ans(tr-1, n) <= x) tr--;
	for(int l = 1; l <= tl; l++){
		for(int r = max(l + 1, tr); r <= n; r++){
			if(ans(l+1, r-1) > x) continue;
			if(get(1, l, 0) + a[l] + get(r, n, 1) - a[r] + C > x) continue;
			if(get(tl+1, r-1, 0) + a[r] + C + get(1, l, 0) + a[l] > x) continue;
			if(get(l+1, tr-1, 1) - a[l] + C + get(r, n, 1) - a[r] > x) continue;
			return 1;
		}
	}
	return 0;
}

long long find_shortcut(int N, std::vector <int> l, std::vector <int> d, int c){
	n = N; C = c;
	for(int i = 1; i <= n; i++){
		b[i] = d[i-1];
		if(i == 1) continue;
		a[i] = a[i-1] + l[i - 2];
	}
	for(int i = 1; i <= n; i++){
		p[0][0][i] = b[i] - a[i];
		p[1][0][i] = b[i] + a[i];
		if(i > 1) lg[i] = lg[i >> 1] + 1;
	}
	for(int c = 0; c < 2; c++){
		for(int k = 1; k <= lg[n]; k++){
			for(int i = 1; i + (1<<k) - 1 <= n; i++){
				p[c][k][i] = max(p[c][k-1][i], p[c][k-1][i+(1<<(k-1))]);
			}
		}
	}
	ll res = ans(1, n);
	for(ll l = 0, r = res - 1; l <= r;){
		ll mid = (l + r) >> 1;
		if(!ok(mid)) l = mid + 1;
		else r = mid - 1, res = mid;
	}
	return res;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB n = 4, 80 is a correct answer
2 Correct 2 ms 18780 KB n = 9, 110 is a correct answer
3 Correct 1 ms 14684 KB n = 4, 21 is a correct answer
4 Correct 1 ms 10588 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 10588 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -