Submission #729405

#	Time	Username	Problem	Language	Result	Execution time	Memory
729405		scanhex	Shortcut (IOI16_shortcut)	C++17	0 / 100	0 ms	212 KiB

shortcut

#include <vector>
#include <climits>
#include <iostream>
#include <algorithm>

#include "shortcut.h"

using namespace std;
typedef long long nagai;
nagai INF = LLONG_MAX / 4;

struct rekt
{
	nagai x1, y1, x2, y2;
	rekt(nagai x1, nagai y1, nagai x2, nagai y2)
		: x1(x1), y1(y1), x2(x2), y2(y2)
	{}
};

rekt isc(rekt a, rekt b)
{
	return rekt(max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2));
}

void to_new(nagai& x, nagai& y)
{
	nagai x1 = x + y;
	nagai y1 = x - y;
	x = x1;
	y = y1;
}

void to_old(nagai& x, nagai& y)
{
	nagai ox = (x + y) / 2;
	nagai oy = x - ox;
	x = ox;
	y = oy;
}

int C = 25;

vector<vector<nagai>> sp;
vector<int> pow;

void init_sp(int n, vector<nagai> x, vector<int> d)
{
	pow.resize(n + 1);
	for (int i = 2; i <= n; ++i)
		pow[i] = pow[i >> 1] + 1;
	sp.assign(C, vector<nagai>(n));
	for (int i = 0; i < n; ++i)
		sp[0][i] = x[i] - d[i];
	for (int i = 0; i < C - 1; ++i)
		for (int j = 0; j < n; ++j)
			sp[i + 1][j] = min(sp[i][j], sp[i][min(j + (1 << i), n - 1)]);
}

nagai query(int L, int R)
{
	int p = pow[R - L];
	return min(sp[p][L], sp[p][R - (1 << p)]);
}

bool kek(int n, vector<nagai> x, vector<int> d, int c, nagai M)
{
	nagai maxjdown = -1, minjup = -1, mxdown = -INF, mnup = INF;
	rekt ans = {-INF, -INF, INF, INF};
	int curp = 0;
	for (int i = 0; i < n; ++i)
	{
		while (curp < i && (x[i] - x[curp] + d[i] + d[curp] > M || query(curp, i) < x[curp] - d[curp]))
		{
			if (x[curp] + d[curp] < mnup)
				mnup = x[curp] + d[curp], minjup = curp;
			if (x[curp] - d[curp] > mxdown)
				mxdown = x[curp] - d[curp], maxjdown = curp;
			++curp;
		}
		if (maxjdown == -1)
			continue;
		nagai x1 = x[i];
		nagai x2 = x[i];
		nagai y2 = x[maxjdown] + M - c - d[i] - d[maxjdown];
		nagai y1 = x[minjup] - (M - c - d[i] - d[minjup]);
		if (y1 > y2)
			return false;
		to_new(x1, y1);
		to_new(x2, y2);
		swap(y1, y2);

		rekt nrekt(x1, y1, x2, y2);
		ans = isc(ans, nrekt);
	}
	curp = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			nagai x1 = x[i];
			nagai y1 = x[j];
			to_new(x1, y1);
			if (ans.x1 <= x1 && x1 <= ans.x2 && ans.y1 <= y1 && y1 <= ans.y2)
				return true;
		}
	}
	return false;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	vector<nagai> x(n);
	x[0] = 0;
	for (int i = 0; i < n - 1; ++i)
		x[i + 1] = x[i]+ l[i];
	init_sp(n, x, d);
	nagai L = 0, R = INF;
	while (R - L > 1)
	{
		nagai M = (L + R) / 2;
		(kek(n, x, d, c, M) ? R : L) = M;
	}
    return R;
}

Compilation message (stderr)

shortcut.cpp:44:13: warning: built-in function 'pow' declared as non-function [-Wbuiltin-declaration-mismatch]
   44 | vector<int> pow;
      |             ^~~

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