oj.uz

Submission #240523

# Submission time Handle Problem Language Result Execution time Memory
240523 2020-06-19T20:45:53 Z Aldas25 Shortcut (IOI16_shortcut) C++14
0 / 100
 5 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;

const int MAXN = 100100;
const ll INF = 1e17;

int n;
ll c;
ll l[MAXN];
ll d[MAXN];
ll x[MAXN];

vl xs;
ll a[MAXN], b[MAXN];
vector<pair<ll, int>> srtB, srtA;

int idToUpd[MAXN], idToGet[MAXN];

ll tree[4 * MAXN][4];

void build (int index, int id = 1, int le = 0, int ri = n - 1) {
	if (le == ri) {
		tree[id][index] = -INF;
		return;
	}

	int mid = (le + ri) / 2;
	build (index, 2 * id, le, mid);
	build (index, 2 * id + 1, mid + 1, ri);
	tree[index][id] = max(tree[index][2 * id], tree[index][2 * id + 1]);
}

void upd (int index, int p, ll kx, int id = 1, int le = 0, int ri = n - 1) {
	if (le == ri) {
		tree[id][index] = kx;
		return;
	}

	int mid = (le + ri) / 2;

	if (p <= mid) {
		upd(index, p, kx, 2 * id, le, mid);
	}
	else {
		upd(index, p, kx, 2 * id + 1, mid + 1, ri);
	}

	tree[id][index] = max(tree[2 * id][index], tree[2 * id + 1][index]);
}

ll get (int index, int kx, int y, int id = 1, int le = 0, int ri = n - 1) {
	if (kx > ri || y < le) {
		return 0ll;
	}

	if (kx <= le && ri <= y) {
		return tree[id][index];
	}

	int mid = (le + ri) / 2;
	return max(get(index, kx, y, 2 * id, le, mid), get(index, kx, y, 2 * id + 1, mid + 1, ri));
}



bool doesExist (ll mn1, ll mx1, ll mn2, ll mx2) {
	/*FOR(y, 0, n-1) FOR(z, 0, n-1) {
	    if (mn1 <= x[y]+x[z] && x[y]+x[z] <= mx1 && mn2 <= x[z]-x[y] && x[z]-x[y] <= mx2)
	        return true;
	}
	return false;*/

	FOR(z, 0, n - 1) {
		ll mnY = max(mn1 - x[z], x[z] - mx2);
		ll mxY = min(mx1 - x[z], x[z] - mn2);

		auto it = lower_bound(xs.begin(), xs.end(), mnY);

		if (it != xs.end()) {
			ll num = (*it);

			if (num <= mxY) {
				return true;
			}
		}

	}

	return false;

}

bool check (ll k) {
	//cout << "----------------------\nk = " << k << endl;

	ll mn1 = -INF, mn2 = -INF, mx1 = INF, mx2 = INF;
	//ll mnA = INF, mxA = -INF, mnB = INF, mxB = -INF;
	//FOR(i, 0, 3) build(i);
	FOR(i, 1, 2) build(i);

	//int rId = 0;
	FOR(i, 0, n - 1) {
		idToUpd[srtB[i].s] = i;
		//cout << "   i=" << i << " srtB = " << srtB[i].f << " id=" << srtB[i].s << endl;
		// while (rId < n && srtA[rId].f - k <= srtB[i].s) {
		//     idToGet[srtA[rId].s] = i-1;
		//     rId++;
		// }
	}

	// int le = 0;
	FOR(j, 0, n - 1) {

		int kj = 0;

		int le = 0, ri = n - 1;

		while (le < ri) {
			int mid = (le + ri + 1) / 2;

			//cout << "   "  << srtB[mid].f  << "     " << a[j]-k << endl;
			if (srtB[mid].f < a[j] - k) {
				le = mid;
			}
			else {
				ri = mid - 1;
			}
		}

		//le = min(le, ri);
		if (a[j] - k <= srtB[le].f) {
			le--;
		}

		//cout << "   j=" << j << " aj-k=" << a[j]-k << "  le= " << le << endl;

		kj = le;

		//ll mnA = (-1ll)*(get(0, 0,kj));
		ll mxA = (get(1, 0, kj));
		ll mnB = (-1ll) * (get(2, 0, kj));
		// ll mxB = (get(3, 0,kj));

		//cout << "  j=" << j

		if (mxA > 0) {
			mn1 = max(mn1, mxA + a[j] - (k - c));
			//mn1 = max(mn1, mnA + a[j] - (k-c));
			mx1 = min(mx1, mnB + b[j] + (k - c));
			//mx1 = min(mx1, mxB + b[j] + (k-c));
			mn2 = max(mn2, a[j] - mnB - (k - c));
			//mn2 = max(mn2, a[j] - mxB - (k-c));
			mx2 = min(mx2, b[j] - mxA + (k - c));
			//mx2 = min(mx2, b[j] - mnA + (k-c));
		}


		kj = idToUpd[j];
		// upd(0, kj, (-a[j]));
		upd(1, kj, (a[j]));
		upd(2, kj, (-b[j]));
		//  upd(3, kj, (b[j]));
	}

	return doesExist(mn1, mx1, mn2, mx2);
}

ll solve () {
	x[0] = 0;
	FOR(i, 1, n - 1) x[i] = x[i - 1] + l[i - 1];
	FOR(i, 0, n - 1) xs.pb(x[i]);

	FOR(i, 0, n - 1) a[i] = x[i] + d[i];
	FOR(i, 0, n - 1) b[i] = x[i] - d[i];
	FOR(i, 0, n - 1) srtA.pb({a[i], i});
	FOR(i, 0, n - 1) srtB.pb({b[i], i});

	sort(srtA.begin(), srtA.end());
	sort(srtB.begin(), srtB.end());

	ll le = 0, ri = 2 * (1e14);

	while (le < ri) {
		ll mid = (le + ri) / 2;

		if (check(mid)) {
			ri = mid;
		}
		else {
			le = mid + 1;
		}
	}

	return le;
}

long long find_shortcut(int _n,vector<int> _l,vector<int> _d,int _c) {
    n = _n;
    c = _c;
    FOR(i, 0, n-2) l[i] = _l[i];
    FOR(i, 0, n-1) d[i] = _d[i];

    return solve();
}

/*inline int read()
{
	int x=0,f=1;char ch=getchar();
	//while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}*/

/*int main()
{
	//FAST_IO;

	//cin >> n >> c;
	//FOR(i, 0, n - 2) cin >> l[i];
	//FOR(i, 0, n - 1) cin >> d[i];*
	n = read();
	c = read();
	FOR(i, 0, n-2) l[i] = read();
	FOR(i, 0, n-1) d[i] = read();

	cout << solve() << "\n";

	return 0;
}*/


/*

4 10
10 20 20
0 40 0 30
ans: 80

9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
ans: 110

4 1
2 2 2
1 10 10 1
ans: 21

3 3
1 1
1 1 1
ans: 4

*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 428 KB n = 4, 80 is a correct answer
2 Correct 5 ms 384 KB n = 9, 110 is a correct answer
3 Correct 5 ms 384 KB n = 4, 21 is a correct answer
4 Correct 5 ms 384 KB n = 3, 4 is a correct answer
5 Correct 5 ms 512 KB n = 2, 62 is a correct answer
6 Correct 5 ms 384 KB n = 2, 3 is a correct answer
7 Incorrect 5 ms 384 KB n = 3, incorrect answer: jury 29 vs contestant 20
8 Halted 0 ms 0 KB -