oj.uz

답안 #24588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24588 2017-06-10T14:11:10 Z gs14004 Shortcut (IOI16_shortcut) C++11
0 / 100
 0 ms 33272 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];

struct seg1{
	lint tree[1000005];
	void init(){
		fill(tree + 1, tree + n + 1, -1e18);
	}
	void upd(int x, lint v){
		while(x <= n){
			tree[x] = max(tree[x], v);
			x += x & -x;
		}
	}
	lint query(int x){
		x = n;
		lint ret = -1e18;
		while(x){
			ret = max(ret, tree[x]);
			x -= x & -x;
		}
		return ret;
	}
}seg1;

struct seg2{
	lint tree[1000005];
	void init(){
		fill(tree + 1, tree + n + 1, 1e18);
	}
	void upd(int x, lint v){
		while(x <= n){
			tree[x] = min(tree[x], v);
			x += x & -x;
		}
	}
	lint query(int x){
		x = n;
		lint ret = 1e18;
		while(x){
			ret = min(ret, tree[x]);
			x -= x & -x;
		}
		return ret;
	}
}seg2;

vector<pi> v, w;

bool trial(lint x){
	lint ps = -1e18, pe = 1e18, ms = -1e18, me = 1e18;
	seg1.init();
	seg2.init();
	int p = 0;
	for(int i=0; i<n; i++){
		while(p < n && w[p].first + x < v[i].first){
			seg1.upd(w[p].second + 1, a[w[p].second] + b[w[p].second]);
			seg2.upd(w[p].second + 1, -a[w[p].second] + b[w[p].second]);
			p++;
		}
		ps = max(ps, seg1.query(v[i].second) - x + c + b[v[i].second] + a[v[i].second]);
		pe = min(pe, seg2.query(v[i].second) + x - c + b[v[i].second] - a[v[i].second]);
		ms = max(ms, seg1.query(v[i].second) - x + c - b[v[i].second] + a[v[i].second]);
		me = min(me, seg2.query(v[i].second) + x - c - b[v[i].second] - a[v[i].second]);
	}
	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);
		if(s <= e && upper_bound(b, b+n, e) != lower_bound(b, b+n, s)) 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.push_back(pi(a[i] + b[i], i));
	for(int i=0; i<n; i++) w.push_back(pi(-a[i] + b[i], i));
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	lint s = 0, e = 1e16;
	while(s != e){
		lint m = (s+e)/2;
		if(trial(m)) e = m;
		else s = m+1;
	}
	return s;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 33272 KB n = 4, 80 is a correct answer
2 Correct 0 ms 33272 KB n = 9, 110 is a correct answer
3 Correct 0 ms 33272 KB n = 4, 21 is a correct answer
4 Correct 0 ms 33272 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 33272 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -