oj.uz

Submission #529242

# Submission time Handle Problem Language Result Execution time Memory
529242 2022-02-22T14:19:30 Z blue Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 1156388 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]);
		}
	}


	vll res(1 + Q, 0);

	vi queries[1 + pct][1 + mct];

	for(int j = 1; j <= Q; j++)
	{
		if(P[j] + X[j] > ypx.back()) continue;

		if(P[j] - X[j] > ymx.back()) continue;

		int plo = 1, phi = pct;
		while(plo != phi)
		{
			int mid = (plo + phi)/2;

			if(ypx[mid] < P[j] + X[j])
				plo = mid+1;
			else
				phi = mid;
		}


		int mlo = 1, mhi = mct;
		while(mlo != mhi)
		{
			int mid = (mlo + mhi)/2;

			if(ymx[mid] < P[j] - X[j])
				mlo = mid+1;
			else
				mhi = mid;
		}

		queries[plo][mlo].push_back(j);
	}




	// for(int mi = 1; mi <= mct; mi++)
	// {
	// 	cht CHT;

	// 	for(int pi = 1; pi <= pct; pi++)
	// 	{
	// 		CHT.insert(horiz_basic[pi][mi - 1], dp[pi][mi]);



	// 		for(int qr : queries[mi][pi])
	// 		{
	// 			res[qr] = max(res[qr], CHT.query((ymx[mi] - (P[qr] - X[qr]))/2));
	// 		}
	// 	}
	// }






	// 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;
		res[j] = 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++;

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

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


	for(int j = 1; j <= Q; j++) cout << res[j] << '\n';


}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25071 ms 672876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 1153872 KB Output is correct
2 Correct 736 ms 1154056 KB Output is correct
3 Correct 677 ms 1138680 KB Output is correct
4 Correct 25 ms 48300 KB Output is correct
5 Correct 757 ms 1153876 KB Output is correct
6 Correct 692 ms 1153852 KB Output is correct
7 Correct 761 ms 1152500 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 1153872 KB Output is correct
2 Correct 736 ms 1154056 KB Output is correct
3 Correct 677 ms 1138680 KB Output is correct
4 Correct 25 ms 48300 KB Output is correct
5 Correct 757 ms 1153876 KB Output is correct
6 Correct 692 ms 1153852 KB Output is correct
7 Correct 761 ms 1152500 KB Output is correct
8 Correct 862 ms 1154076 KB Output is correct
9 Correct 870 ms 1154100 KB Output is correct
10 Correct 670 ms 1136664 KB Output is correct
11 Correct 31 ms 48452 KB Output is correct
12 Correct 875 ms 1153888 KB Output is correct
13 Correct 960 ms 1154140 KB Output is correct
14 Correct 998 ms 1153960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 1153872 KB Output is correct
2 Correct 736 ms 1154056 KB Output is correct
3 Correct 677 ms 1138680 KB Output is correct
4 Correct 25 ms 48300 KB Output is correct
5 Correct 757 ms 1153876 KB Output is correct
6 Correct 692 ms 1153852 KB Output is correct
7 Correct 761 ms 1152500 KB Output is correct
8 Correct 862 ms 1154076 KB Output is correct
9 Correct 870 ms 1154100 KB Output is correct
10 Correct 670 ms 1136664 KB Output is correct
11 Correct 31 ms 48452 KB Output is correct
12 Correct 875 ms 1153888 KB Output is correct
13 Correct 960 ms 1154140 KB Output is correct
14 Correct 998 ms 1153960 KB Output is correct
15 Correct 3335 ms 1156260 KB Output is correct
16 Correct 3360 ms 1156388 KB Output is correct
17 Correct 1115 ms 1141448 KB Output is correct
18 Correct 70 ms 48964 KB Output is correct
19 Correct 2560 ms 1154912 KB Output is correct
20 Correct 3614 ms 1154996 KB Output is correct
21 Correct 4026 ms 1155124 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25071 ms 672876 KB Time limit exceeded
2 Halted 0 ms 0 KB -