제출 #529254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529254		blue	Bodyguard (JOI21_bodyguard)	C++17	7 / 100	1313 ms	739600 KiB

bodyguard

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;


const int maxN = 2'800;

int N;

vll T(1 + maxN), A(1 + maxN), B(1 + maxN), C(1 + maxN);



const int maxQ = 3'000'000;

int Q;

vll P(1 + maxQ), X(1 + maxQ);






























const ll INF = 1'000'000'000'000'000'000LL;

struct slope_line
{
	double e;

	ll a;
	ll b;
};

bool operator < (slope_line A, slope_line B)
{
	return A.a < B.a;
}

struct point_line
{
	double e;

	ll a;
	ll b;
};

bool operator < (point_line A, point_line B)
{
	return A.e < B.e;
}

double get_intersect(ll a1, ll b1, ll a2, ll b2)
{
	return double(b1 - b2) / double(a2 - a1);
}


bool good(ll a0, ll b0, ll a, ll b, ll a1, ll b1)
{
	return double(b0 - b) / double(a - a0) < double(b - b1) / double(a1 - a);
}


struct cht
{	
	multiset<slope_line> sl;
	multiset<point_line> pl;

	ll query(ll x)
	{
		if(pl.empty()) return 0;

		auto it = pl.lower_bound({double(x), 0, 0});

		// 

		// cerr << it->a << ' ' << it->b << '\n';

		// for(auto& plv : pl) cerr << plv.e << ' ' << plv.a << ' ' << plv.b << "   ";
		// 	cerr << '\n';

		return it->a * x  +  it->b;
	}

	void insert(ll a, ll b)
	{
		// cerr << "inserting " << a << ' ' << b << '\n';
		multiset<slope_line>::iterator it, nxt, prv, nxt2, prv2;

		it = sl.lower_bound({-1, a, b});

		if(it != sl.end() && it->a == a && it->b >= b) return;

		// cerr << "check\n";

		if(it != sl.end() && it->a == a) 
		{
			pl.erase({it->e, it->a, it->b});
			sl.erase(it);
		}

		sl.insert({-1, a, b});

		// cerr << "hello\n";
// 



		it = sl.find({-1, a, b});
		nxt = it;
		nxt++;

		// cerr << "why\n";

		if(nxt != sl.end())
		{
			prv = it;
			if(prv != sl.begin())
			{
				prv--;

				ll a0 = prv->a, b0 = prv->b;
				ll a1 = nxt->a, b1 = nxt->b;

				/*
					a0 * int0 + b0 == a * int0 + b
					int0 = (b - b0) / (a0 - a)
					     = (b0 - b) / (a - a0)

					int1 = (b1 - b) / (a - a1)
					     = (b - b1) / (a1 - a)



					int0 < int1 => (b0 - )
				*/

				if(!good(a0, b0, a, b, a1, b1))
				{
					return;
				}
				// cerr << "passed\n";
			}
		}

		// cerr << "cleared\n";



		while(1)
		{
			nxt = sl.find({-1, a, b});
			nxt++;

			if(nxt == sl.end()) break;

			nxt2 = nxt;
			nxt2++;

			if(nxt2 == sl.end()) break;

			if(good(a, b, nxt->a, nxt->b, nxt2->a, nxt2->b)) break;

			sl.erase(nxt);
			pl.erase({nxt->e, nxt->a, nxt->b});
		}

		while(1)
		{
			prv = sl.find({-1, a, b});
			
			if(prv == sl.begin()) break;
			prv--;


			prv2 = prv;
			if(prv2 == sl.begin()) break;
			prv2--;

			if(good(prv2->a, prv2->b, prv->a, prv->b, a, b)) break;

			ll prv2a = prv2->a;
			ll prv2b = prv2->b;
			double prv2e = get_intersect(a, b, prv2->a, prv2->b);

			sl.erase(prv);
			pl.erase({prv->e, prv->a, prv->b});

			sl.erase(prv2);
			pl.erase({prv2->e, prv2->a, prv2->b});

			sl.insert({prv2e, prv2a, prv2b});
			pl.insert({prv2e, prv2a, prv2b});
		}


		double endv, startv;



		nxt = sl.find({-1, a, b});
		nxt++;

		if(nxt == sl.end()) endv = 2'000'000'005;
		else
		{
			// cerr << "#\n";
			// cerr << a << ' ' << b << " : " << nxt->a << ' ' << nxt->b << '\n';
			endv = double(nxt->b - b) / double(a - nxt->a);

			// cerr << endv << '\n';
		}

		// cerr << "endv = " << endv << '\n';


		prv = sl.find({-1, a, b});
		if(prv != sl.begin())
		{
			// cerr << "entered\n";
			prv--;

			startv = double(prv->b - b) / double(a - prv->a);

			slope_line new_prev = {startv, prv->a, prv->b};

			// cerr << "hello\n";

			// cerr << "why\n";


			// for(auto& plv : pl)
			// {
			// 	cerr << plv.e << ' ' << plv.a << ' ' << plv.b << " | ";
			// }
			// cerr << '\n';

			// cerr << "nv = " << prv->e << ' ' << prv->a << ' ' << prv->b << '\n';

			pl.erase({prv->e, prv->a, prv->b});
			// cerr << "checking\n";

			sl.erase(prv);


			sl.insert(new_prev);
			pl.insert({new_prev.e, new_prev.a, new_prev.b});
		}


		sl.erase({-1, a, b});
		sl.insert({endv, a, b});
		pl.insert({endv, a, b});

		// cerr << "final line = " << endv << ' ' << a << ' ' << b << '\n';
	}
};









































int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> Q; if(Q > 40000) assert(0);
	for(int i = 1; i <= N; i++)
	{
		cin >> T[i] >> A[i] >> B[i] >> C[i];

		T[i] *= 2;
		A[i] *= 2;
		B[i] *= 2;
		C[i] /= 2;
	}

	for(int j = 1; j <= Q; j++)
	{
		cin >> P[j] >> X[j];
		P[j] *= 2;
		X[j] *= 2;
	}


	map<ll, ll> ypx_map, ymx_map;
	for(int i = 1; i <= N; i++)
	{
		ypx_map[T[i] + A[i]] = 0;
		ymx_map[T[i] - A[i]] = 0;

		ypx_map[(T[i] + abs(A[i] - B[i])) + B[i]] = 0;
		ymx_map[(T[i] + abs(A[i] - B[i])) - B[i]] = 0;
	}

	ll pct = 0, mct = 0;

	vll ypx{-2'000'000'002LL};
	vll ymx{-2'000'000'002LL};

	for(auto& z : ypx_map) 
	{
		z.second = ++pct;
		ypx.push_back(z.first);
	}

	for(auto& z : ymx_map) 
	{
		z.second = ++mct;
		ymx.push_back(z.first);
	}

	vi start_ypx(1 + N), start_ymx(1 + N), end_ypx(1 + N), end_ymx(1 + N);
	for(int i = 1; i <= N; i++)
	{
		start_ypx[i] = ypx_map[T[i] + A[i]];
		start_ymx[i] = ymx_map[T[i] - A[i]];

		end_ypx[i] = ypx_map[T[i] + abs(A[i] - B[i]) + B[i]];
		end_ymx[i] = ymx_map[T[i] + abs(A[i] - B[i]) - B[i]];
	}




	//i = ypx, j = ymx

	vvll horiz(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1)
	vvll vert(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j)

	vvll horiz_basic(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1)
	vvll vert_basic(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j)

	for(int i = 1; i <= N; i++)
	{
		if(B[i] < A[i])
		{
			for(int j = start_ymx[i]; j < end_ymx[i]; j++)
			{
				// cerr << start_ypx[i] << " ! " << j << '\n';
				horiz_basic[ start_ypx[i] ][j] = max(horiz_basic[ start_ypx[i] ][j], C[i]);
				// horiz[ start_ypx[i] ][j] = max(horiz[start_ypx[i]][j], (ymx[j+1] - ymx[j])/2  *  C[i]);
				horiz[start_ypx[i]][j] = horiz_basic[start_ypx[i]][j] * (ymx[j+1] - ymx[j]) / 2;

				// cerr << ymx[j+1] << ' ' << ymx[j] << ' ' << C[i] << '\n';

				// cerr << horiz[start_ypx[i]][j] << '\n';
			}
		}
		else
		{
			for(int j = start_ypx[i]; j < end_ypx[i]; j++)
			{

				vert_basic[j][ start_ymx[i] ] = max(vert_basic[j][start_ymx[i]], C[i]);
				vert[j][ start_ymx[i] ] = (ypx[j+1] - ypx[j])/2  *  vert_basic[ j ][ start_ymx[i] ];
			}
		}
	}



	// cerr << "\n\n\n!!!\n";

	// cerr << pct << ' ' << mct << '\n';
	// for(int i = 1; i <= N; i++)
	// {
	// 	cerr << T[i] << ' ' << A[i] << ' ' << B[i] << ' ' << C[i] << '\n';
	// }

	// for(int i = 1; i <= pct; i++)
	// {
	// 	for(int j = 1; j <= mct; j++) cerr << horiz[i][j] << ' ';
	// 		cerr << '\n';
	// }
	// cerr << "----\n";
	// for(int i = 1; i <= pct; i++)
	// {
	// 	for(int j = 1; j <= mct; j++) cerr << vert[i][j] << ' ';
	// 		cerr << '\n';
	// }




	vvll dp(1 + pct, vll(1 + mct, 0));


	for(int i = pct; i >= 1; i--)
	{
		for(int j = mct; j >= 1; j--)
		{
			if(i < pct) dp[i][j] = max(dp[i][j], dp[i+1][j] + vert[i][j]);

			if(j < mct) dp[i][j] = max(dp[i][j], dp[i][j+1] + horiz[i][j]);
		}
	}


	// for(int i = 1; i <= pct; i++)
	// {
	// 	for(int j = 1; j <= mct; j++)
	// 	{
	// 		cerr << dp[i][j] << ' ';
	// 	}
	// 	cerr << '\n';
	// }


	for(int j = 1; j <= Q; j++)
	{
		ll res = 0;

		if(P[j] + X[j] <= ypx.back())
		{
			if(P[j] - X[j] <= ymx.back())
			{
				int pi = 0, mi = 0;
				while(ypx[pi] < P[j] + X[j])
					pi++;

				while(ymx[mi] < P[j] - X[j])
					mi++;

				cht pv;

				for(int pi2 = pi; pi2 <= pct; pi2++)
				{
					// res = max(res, dp[pi2][mi] + (ymx[mi] - (P[j] - X[j]))/2 * horiz_basic[pi2][mi - 1]);
					//                              ymx[mi] * horiz_basic[pi2][mi-1]  -  (P)
					// pv.insert(- horiz_basic[pi2][mi - 1], dp[pi2][mi] + (ymx[mi] * horiz_basic[pi2][mi - 1]));

					pv.insert(horiz_basic[pi2][mi - 1], dp[pi2][mi]);

					// cerr << "inserting line " << 
				}

				res = max(res, pv.query((ymx[mi] - (P[j] - X[j]))/2));

				for(int mi2 = mi; mi2 <= mct; mi2++)
				{
					res = max(res, dp[pi][mi2] + (ypx[pi] - (P[j] + X[j]))/2 * vert_basic[pi - 1][mi2]);
				}
			}
		}

		cout << res << '\n';
	}


}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52