Submission #134791

#	Time	Username	Problem	Language	Result	Execution time	Memory
134791		MAMBA	Shortcut (IOI16_shortcut)	C++17	38 / 100	2031 ms	504 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

inline bool smax(ll &a, ll b) {
	if (a < b) {
		a= b;
		return true;
	}
	return false;
}

inline bool smin(ll &a, ll b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

ll find_shortcut(int n, vi D, vi I, int c)
{
	ll res = 1e18;

	vl pos(n);
	rep(i , 1 , n) pos[i] = pos[i - 1] + D[i - 1];

	vl gg(n), dd(n);

	{
		vi ts;
		rep(i , 0 , n) {
			gg[i] = i ? gg[i - 1]  : 0;
			if (ts.size())
				smax(gg[i] , pos[i] - pos[ts[0]] + I[i] + I[ts[0]]);
			while (ts.size() && pos[i] - pos[ts.back()] + I[ts.back()] <= I[i])
				ts.pop_back();


			ts.push_back(i);
		}
	}


	{
		vi ts;
		for (int i = n - 1; ~i; i--) {
			dd[i] = i + 1 < n ? dd[i + 1]  : 0;
			if (ts.size())
				smax(dd[i] , -(pos[i] - pos[ts[0]]) + I[i] + I[ts[0]]);
			while (ts.size() && -(pos[i] - pos[ts.back()]) + I[ts.back()] <= I[i])
				ts.pop_back();
			ts.push_back(i);
		}
	}



	auto f = [&](int l , int r) -> ll {

		vl junk(I.begin() + l , I.begin() + r + 1);
		rep(i , 0 , l) smax(junk[0] , I[i] + pos[l] - pos[i]);
		rep(i , r + 1, n) smax(junk.back() , I[i] + pos[i] - pos[r]);

		ll len = pos[r] - pos[l] + c;

		ll rr = max(gg[l] , dd[r]);


		deque<int> st;

		auto dist = [&](int l_ , int r_) -> ll {
			ll local = pos[r_] - pos[l_];
			if (l_ >= r_) local += len;
			return local;
		};

		auto push = [&](int p) {
			while (st.size()) {
				int u = st.back();
				if (u == p || dist(u , p) + junk[u - l] <= junk[p - l])
					st.pop_back();
				else break;
			}
			st.push_back(p);
		};

		auto relax = [&](int p) {

			while (st.size() && dist(st.front() , p) * 2 > len)
				st.pop_front();

		};

		rep(i , l , r + 1) {
			relax(i);
			push(i);
		}
		rep(i , l , r + 1) {
			relax(i);
			if (st.size()) {
				int u = st.front();
				ll shit = junk[u - l] + junk[i - l] + dist(u , i);
				smax(rr , shit);
			}
			push(i);
		}
		return rr;
	};

	rep(i , 0 , n)
		rep(j , i + 1, n)
				smin(res , f(i , j));

	return res;

}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3