oj.uz

Submission #24621

# Submission time Handle Problem Language Result Execution time Memory
24621 2017-06-10T18:44:23 Z gs14004 Shortcut (IOI16_shortcut) C++11
0 / 100
 0 ms 48900 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;

int n, c;
lint a[1000005], b[1000005];
pi v[1000005], w[1000005];

bool trial(lint x){
	lint ps = -1e18, pe = 1e18, ms = -1e18, me = 1e18;
	lint mx = -1e18, mxp = -1, smx = -1e18;
	lint mn = 1e18, mnp = -1, smn = 1e18;
	int p = 0;
	for(int i=0; i<n; i++){
		while(p < n && w[p].first + x < v[i].first){
			lint cmx = a[w[p].second] + b[w[p].second];
			lint cmn = -a[w[p].second] + b[w[p].second];
			if(mx < cmx){
				smx = mx;
				mx = cmx;
				mxp = w[p].second;
			}
			if(mn > cmn){
				smn = mn;
				mn = cmn;
				mnp = w[p].second;
			}
			p++;
		}
		lint q1 = (v[i].second == mxp ? mx : smx);
		lint q2 = (v[i].second == mnp ? mn : smn);
		lint ca = a[v[i].second];
		lint cb = b[v[i].second];
		ps = max(ps, q1 - x + c + cb + ca);
		pe = min(pe, q2 + x - c + cb - ca);
		ms = max(ms, q1 - x + c - cb + ca);
		me = min(me, q2 + x - c - cb - ca);
	}
	p = 0;
	for(int i=0; i<n; i++){
		lint s = max(ps - b[i], b[i] - me);
		lint e = min(pe - b[i], b[i] - ms);
		while(p < n && s > b[p]) p++;
		while(p > 0 && s <= b[p-1]) p--;
		while(p < n && b[p] <= e) return true;
	}
	return false;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	::n = n;
	::c = c;
	for(int i=0; i<n; i++){
		a[i] = d[i];
		if(i >= 1) b[i] = b[i-1] + l[i-1];
	}
	for(int i=0; i<n; i++){
		v[i] = pi(a[i] + b[i], i);
		w[i] = pi(-a[i] + b[i], i);
	}
	sort(v, v+n);
	sort(w, w+n);
	lint s = 0, e = 2e15;
	while(s != e){
		lint m = (s+e)/2;
		if(trial(m)) e = m;
		else s = m+1;
	}
	return s;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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