oj.uz

답안 #529228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529228 2022-02-22T13:47:25 Z blue Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 740400 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
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;
	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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 25047 ms 388336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 739436 KB Output is correct
2 Correct 445 ms 739560 KB Output is correct
3 Correct 417 ms 730080 KB Output is correct
4 Correct 21 ms 48076 KB Output is correct
5 Correct 480 ms 739324 KB Output is correct
6 Correct 430 ms 739396 KB Output is correct
7 Correct 497 ms 738500 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 739436 KB Output is correct
2 Correct 445 ms 739560 KB Output is correct
3 Correct 417 ms 730080 KB Output is correct
4 Correct 21 ms 48076 KB Output is correct
5 Correct 480 ms 739324 KB Output is correct
6 Correct 430 ms 739396 KB Output is correct
7 Correct 497 ms 738500 KB Output is correct
8 Correct 1297 ms 739484 KB Output is correct
9 Correct 1317 ms 739684 KB Output is correct
10 Correct 506 ms 728676 KB Output is correct
11 Correct 28 ms 48076 KB Output is correct
12 Correct 624 ms 739436 KB Output is correct
13 Correct 2218 ms 739596 KB Output is correct
14 Correct 817 ms 739408 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 739436 KB Output is correct
2 Correct 445 ms 739560 KB Output is correct
3 Correct 417 ms 730080 KB Output is correct
4 Correct 21 ms 48076 KB Output is correct
5 Correct 480 ms 739324 KB Output is correct
6 Correct 430 ms 739396 KB Output is correct
7 Correct 497 ms 738500 KB Output is correct
8 Correct 1297 ms 739484 KB Output is correct
9 Correct 1317 ms 739684 KB Output is correct
10 Correct 506 ms 728676 KB Output is correct
11 Correct 28 ms 48076 KB Output is correct
12 Correct 624 ms 739436 KB Output is correct
13 Correct 2218 ms 739596 KB Output is correct
14 Correct 817 ms 739408 KB Output is correct
15 Correct 12390 ms 740144 KB Output is correct
16 Correct 12097 ms 740400 KB Output is correct
17 Correct 1925 ms 731456 KB Output is correct
18 Correct 59 ms 48324 KB Output is correct
19 Correct 2348 ms 739884 KB Output is correct
20 Correct 24042 ms 739992 KB Output is correct
21 Correct 4565 ms 740120 KB Output is correct

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 25047 ms 388336 KB Time limit exceeded
2 Halted 0 ms 0 KB -