oj.uz

Submission #603007

# Submission time Handle Problem Language Result Execution time Memory
603007 2022-07-23T14:16:04 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), rig(n), tmp(n), ls(n), rs(n);
	vector<pii> 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] = {rig[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 = lef, rs = rig;
	for (int i = n - 2;i >= 0;i--) {
		ls[i] = max(ls[i], ls[i+1]);
		rs[i] = max(rs[i], rs[i+1]);
	}	
	ll low = 0, up = (ll)(1<<30)*n;

	while (low < up - 1) {
		ll M = (low + up) / 2;
		ll lb = -inf, rb = inf, db = -inf, ub = inf;
		
		for (int i = 0;i < n;i++) {
			int ind = upper_bound(rig.begin(), rig.end(), M - lef[i]) - rig.begin();
			//[ind, n);
			if (ind == n) continue;
			ll len = M - D[i] - C;
			ll l = rs[ind] - len, r = -ls[ind] + len;
			//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);
		}
		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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 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 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 71
6 Halted 0 ms 0 KB -