Submission #1020776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020776		vjudge1	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	14680 KiB

shortcut

// #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];
ll b[maxn];
ll p[2][maxl][maxn];
int lg[maxn];
ll ans[3030][3030];
ll dp[3030][3030];
// struct asd{
// 	ll ans;
// 	ll a, b;
// } d[maxn * 4];

// asd f(asd a, asd b){
// 	asd c;
// 	c.a = max(a.a, b.a);
// 	c.b = max(a.b, b.b);
// 	c.ans = max({a.ans, b.ans, a.a + b.b});
// 	return c;
// }

// void build(int v = 1, int tl = 1, int tr = n){
// 	if(tl == tr){
// 		d[v] = {0, b[tl] - a[tl], b[tl] + a[tl]};
// 	} else{
// 		int mid = (tl + tr) >> 1;
// 		build(v<<1, tl, mid);
// 		build(v<<1|1, mid+1, tr);
// 		d[v] = f(d[v<<1], d[v<<1|1]);
// 	}
// }

// asd ans(int l, int r, int v = 1, int tl = 1, int tr = n){
// 	if(tr < l || tl > r) return {0, -INF, -INF};
// 	if(l <= tl && tr <= r) return d[v];
// 	int mid = (tl + tr) >> 1;
// 	return f(ans(l, r, v<<1, tl, mid)
// 	, ans(l, r, v<<1|1, mid+1, tr));
// }

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]);
}

bool ok(ll x){
	for(int i = 1; i <= n; i++){
		dp[i][i] = INF;
	}
	for(int l = n - 1; l > 0; l--){
		for(int r = l + 1; r <= n; r++){
			dp[l][r] = min(dp[l][r-1], dp[l+1][r]);
			if(a[r] - a[l] + b[l] + b[r] > x){
				dp[l][r] = min(dp[l][r], x-C+a[r]-a[l]-b[l]-b[r]);
			}
		}
	}
	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(l != 2 || r != 9) continue;
			if(a[r] - a[l] > dp[l][r]) continue;
			if(get(1, l-1, 0) + get(r+1, n, 1) + min(0ll, a[l] - a[r] + C) > x) continue;
			if(get(tl+1, r, 0) + a[r] + C + get(1, l-1, 0) + a[l] > x) continue;
			if(get(l, tr-1, 1) - a[l] + C + get(r+1, 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))]);
			}
		}
	}
	for(int l = n - 1; l > 0; l--){
		for(int r = l + 1; r <= n; r++){
			ans[l][r] = max(ans[l][r-1],
				b[r] + a[r] + get(l, r-1, 0));
		}
	}
	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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3