답안 #132329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132329 2019-07-18T17:31:24 Z Noam527 Shortcut (IOI16_shortcut) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

const int mxn = 1e6 + 5;

int n;
ll c;
ll a[mxn] = {}, b[mxn] = {};
bool check[mxn] = {}, check2[mxn] = {};

pair<ll, ll> st[mxn];

pair<ll, ll> calc12(ll D) {
	int sz = 0, nxt1 = 0, nxt2 = 0;
	ll rtn1 = -inf, rtn2 = -inf;
	st[sz++] = { a[0] + b[0], -a[0] + b[0] };
	for (int j = 1; j < n; j++) {
		if (check[j]) {
			nxt2 = min(nxt2, sz - 1);
			while (nxt2 + 1 < sz && c - D + st[nxt2].first - a[j] + b[j] <= rtn2) nxt2++;
			if (c - D + st[nxt2].first - a[j] + b[j] > rtn2) {
				if (st[nxt2].second + a[j] + b[j] > D) {
					while (nxt2 + 1 < sz && st[nxt2 + 1].second + a[j] + b[j] > D) nxt2++;
					rtn2 = max(rtn2, c - D + st[nxt2].first - a[j] + b[j]);
				}
			}
		}
		if (check2[j]) {
			while (nxt1 + 1 < sz && st[nxt1 + 1].second > D - b[j] - a[j]) nxt1++;
			while (nxt1 && st[nxt1].second <= D - b[j] - a[j]) nxt1--;
			if (st[nxt1].second > D - b[j] - a[j])
				rtn1 = max(rtn1, c - D + st[nxt1].first + a[j] + b[j]);
		}
		if (st[sz - 1].first < a[j] + b[j]) {
			while (sz && st[sz - 1].second <= -a[j] + b[j]) sz--;
			st[sz++] = { a[j] + b[j], -a[j] + b[j] };
		}
	}
	return{ rtn1, rtn2 };
}
pair<ll, ll> calc34(ll D) {
	ll rtn3 = inf, rtn4 = inf;
	ll mx = b[0] - a[0];
	for (int j = 1; j < n; j++) {
		if (mx > D - b[j] - a[j]) {
			rtn3 = min(rtn3, D - c - mx + a[j] - b[j]);
			rtn4 = min(rtn4, D - c - mx - a[j] - b[j]);
		}
		mx = max(mx, b[j] - a[j]);
	}
	return{ rtn3, rtn4 };
}
bool can(ll v[5]) {
	ll d[2] = { v[2], v[4] };
	ll s[2] = { v[1], v[3] };
	if (d[0] > d[1] || s[0] > s[1]) return false;

	int dl = 0, dr = 0, sl = n - 1, sr = n - 1; // difference applies on [dl, dr), sum on (sl, sr]
	for (int i = 0; i < n; i++) {
		dl = max(dl, i + 1);
		dr = max(dr, i + 1);
		if (dl > sr) return false;
		while (dl < n && a[i] - a[dl] > d[1]) dl++;
		while (dr < n && a[i] - a[dr] >= d[0]) dr++;
		while (sl > 0 && a[i] + a[sl] >= s[0]) sl--;
		while (sr > 0 && a[i] + a[sr] > s[1]) sr--;
		if (max(dl, sl + 1) <= min(dr - 1, sr))
			return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> c;
	for (int i = 1; i < n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for (int i = 0; i < n; i++) cin >> b[i];

	check[n - 1] = true;
	ll mmx = -a[n - 1] + b[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		if (-a[i] + b[i] > mmx) {
			mmx = -a[i] + b[i];
			check[i] = true;
		}
	}
	check2[n - 1] = true;
	mmx = a[n - 1] + b[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		if (a[i] + b[i] > mmx) {
			mmx = a[i] + b[i];
			check2[i] = true;
		}
	}

	ll v[5];
	ll lo = 0, hi = 1000000000LL * (n + 2), mid;
	pair<ll, ll> p;
	while (lo < hi) {
		mid = (lo + hi) / 2;
		p = calc34(mid);
		v[3] = p.first;
		v[4] = p.second;
		p = calc12(mid);
		v[1] = p.first;
		v[2] = p.second;
		if (can(v)) hi = mid;
		else lo = mid + 1;
	}
	finish(lo);
}

Compilation message

/tmp/ccTpsh9q.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUV4Ngg.o:shortcut.cpp:(.text.startup+0x0): first defined here
/tmp/ccTpsh9q.o: In function `main':
grader.cpp:(.text.startup+0x10d): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status