oj.uz

Submission #603079

# Submission time Handle Problem Language Result Execution time Memory
603079 2022-07-23T14:53:16 Z 8e7 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 212 KB 
#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<58;

long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
	vector<ll> p(n), lef(n+1, -inf), rig(n+1, -inf), tmp(n);
	vector<pii> ls(n), rs(n), a(n);
	for (int i = 1;i < n;i++) p[i] = p[i-1] + L[i-1];
	for (int i = 0;i < n;i++) {
		a[i] = {p[i] + D[i], i};
	}
	sort(a.begin(), a.end());
	for (int i = 0;i < n;i++) {
		int id = a[i].ss;
		lef[i] = D[id] - p[id];
		rig[i] = D[id] + p[id];
		ls[i] = {id, n};
		rs[i] = {id, n};
	}
	for (int i = n - 2;i >= 0;i--) {
		int se = ls[i].ff;
		if (lef[ls[i+1].ff] < lef[se]) {
			se = ls[i+1].ff;
		} else {
			ls[i].ff = ls[i+1].ff;
		}
		if (lef[se] > lef[ls[i+1].ss]) ls[i].ss = se;
		else ls[i].ss = ls[i+1].ss;

		se = rs[i].ff;
		if (rig[rs[i+1].ff] < rig[se]) {
			se = rs[i+1].ff;
		} else {
			rs[i].ff = rs[i+1].ff;
		}
		if (rig[se] > rig[rs[i+1].ss]) rs[i].ss = se;
		else rs[i].ss = rs[i+1].ss;
	}	
	rig.pop_back(), lef.pop_back();
	ll low = 0, up = inf;

	while (low < up - 1) {
		ll M = (low + up) / 2;
		ll lb = -inf, rb = inf, db = -inf, ub = inf;
		
		//debug("M", M);
		for (int i = 0;i < n-1;i++) {
			int ind = upper_bound(rig.begin(), rig.end(), M - (D[i] - p[i])) - rig.begin();
			//[ind, n);
			//debug(i, ind);
			if (ind == n) continue;
			ll len = M - D[i] - C;
			ll l = (rs[ind].ff != i ? rig[rs[ind].ff] : rig[rs[ind].ss]) - len, 
			   r = -(ls[ind].ff != i ? lef[ls[ind].ff] : lef[ls[ind].ss]) + len;
			//debug("l", l, "r", r);
			//square with two points at [l, r]
			lb = max(lb, p[i] - r);
			rb = min(rb, p[i] - l);
			db = max(db, p[i] + l);
			ub = min(ub, p[i] + r);
		}
		//debug(M, lb, rb, db, ub);
		if (rb < lb || ub < db) low = M;
		else {
			bool good = 0;
			for (int i = 0;i < n;i++) {
				ll mi = max(db - p[i], -rb + p[i]);
				ll ma = min(ub - p[i], -lb + p[i]);
				int ind = lower_bound(p.begin(), p.end(), mi) - p.begin();
				if (ind != n && p[ind] <= ma) {
					good = 1;
					break;
				}
			}	
			if (good) up = M;
			else low = M;
		}
	}
	return up;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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