Submission #529546

#	Time	Username	Problem	Language	Result	Execution time	Memory
529546		blue	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	10425 ms	1605076 KiB

bodyguard

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
#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>;
#define sz(x) int(x.size())
 
 
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 lct
// {
// 	ll l;
// 	ll r;
 
// 	bool good;
 
// 	ll a;
// 	ll b;

// 	// int ii, jj;
 
// 	lct* left = NULL;
// 	lct* right = NULL;

// 	lct(vll& xv, ll i, ll j)
// 	{
// 		// ii = i, jj = j;

// 		l = xv[i];
// 		r = xv[j];

// 		good = 1;

// 		a = b = 0;

// 		if(i == j)
// 		{
// 			left = right = NULL;
// 		}
// 		else
// 		{
// 			left = new lct(xv, i, (i+j)/2);
// 			right = new lct(xv, (i+j)/2+1, j);
// 		}
// 	}
 
// 	// lct()
// 	// {
// 	// 	l = 0;
// 	// 	r = 2'000'000'000LL;
 
// 	// 	good = 1;
 
// 	// 	a = b = 0;
 
// 	// 	left = right = NULL;
// 	// }
 
// 	// lct(ll l1, ll r1, bool good1, ll a1, ll b1, lct* left1, lct* right1)
// 	// {
// 	// 	l = l1;
// 	// 	r = r1;
// 	// 	good = good1;
// 	// 	a = a1;
// 	// 	b = b1;
// 	// 	left = left1;
// 	// 	right = right1;
// 	// }
 
// 	void insert(ll na, ll nb)
// 	{
		
// 		if(na * l + nb <= a * l + b && na * r + nb <= a * r + b) return;
 
// 		// cerr << "inserting " << na << ' ' << nb << " into " << l << ' ' << r << '\n';
 
// 		if(na * l + nb >= a * l + b && na * r + nb >= a * r + b) 
// 		{
// 			a = na;
// 			b = nb;
// 			good = 1;
 
// 			// cerr << "setting " << l << ' ' << r << " to " << na <<' ' << nb << '\n';
// 		}
// 		else
// 		{

// 			// cerr << "else : " << (left == NULL) << ' ' << (right == NULL) << ' ' << l << ' ' << r << '\n';
// 			// cerr << ii << ' ' << jj << '\n';
 
// 			// if(left == NULL)
// 			// {
// 			// 	left = new lct{l, (l+r)/2, 1, 0, 0, NULL, NULL};
// 			// }

// 			if(good)
// 				left->insert(a, b);
// 			left->insert(na, nb);
			
// 			// if(right == NULL)
// 			// {
// 			// 	right = new lct{(l+r)/2+1, r, 1, 0, 0, NULL, NULL};
// 			// }

// 			if(good)
// 				right->insert(a, b);
// 			right->insert(na, nb);


// 			good = 0;
// 		}
// 	}
 
// 	ll query(ll x)
// 	{
// 		if(good) return a * x + b;
// 		else if(x <= left->r) return left->query(x);
// 		else return right->query(x);
// 	}
// };

struct lct
{
	vll xv;

	vector<bool> good;
	vector<ll> a;
	vector<ll> b;

	lct(vll& xv_)
	{
		xv = xv_;

		good = vector<bool>((sz(xv) << 2) + 5, 0);
		a = b = vector<ll>((sz(xv) << 2) + 5, 0);

		good[1] = 1;
	}

	void insert(ll na, ll nb, int i, int xi, int xj)
	{
		if(na * xv[xi] + nb <= a[i] * xv[xi] + b[i] && na * xv[xj] + nb <= a[i] * xv[xj] + b[i]) return;

		// cerr << "inserting " << na << ' ' << nb << " over range " << xi << ' '  << xj << " : " << xv[xi] << ' ' << xv[xj] << '\n';
 
		if(na * xv[xi] + nb >= a[i] * xv[xi] + b[i] && na * xv[xj] + nb >= a[i] * xv[xj] + b[i]) 
		{


			// cerr << na << ' ' << nb << ' ' << xv[xi] << " | " << a[i] << ' ' << b[i] << ' ' << xv[xi] << '\n';

			a[i] = na;
			b[i] = nb;
			good[i] = 1;

			// cerr << "done directly\n";
 
			// cerr << "setting " << l << ' ' << r << " to " << na <<' ' << nb << '\n';
		}
		else
		{

			// cerr << "entering further\n";

			// cerr << "else : " << (left == NULL) << ' ' << (right == NULL) << ' ' << l << ' ' << r << '\n';
			// cerr << ii << ' ' << jj << '\n';
 
			// if(left == NULL)
			// {
			// 	left = new lct{l, (l+r)/2, 1, 0, 0, NULL, NULL};
			// }

			if(good[i])
				insert(a[i], b[i], 2*i, xi, (xi+xj)/2);
			insert(na, nb, 2*i, xi, (xi+xj)/2);
			
			// if(right == NULL)
			// {
			// 	right = new lct{(l+r)/2+1, r, 1, 0, 0, NULL, NULL};
			// }

			if(good[i])
				insert(a[i], b[i], 2*i+1, (xi+xj)/2, xj);
			// right->insert(na, nb);
			insert(na, nb, 2*i+1, (xi+xj)/2+1, xj);


			// good = 0;
			good[i] = 0;
		}
	}

	void insert(ll na, ll nb)
	{
		insert(na, nb, 1, 0, sz(xv) - 1);
	}

	ll query(ll x, int i, int xi, int xj)
	{
		if(good[i]) return a[i] * x + b[i];
		else if(x <= xv[(xi+xj)/2]) return query(x, 2*i, xi, (xi+xj)/2);
		else return query(x, 2*i+1, (xi+xj)/2+1, xj);
	}

	ll query(ll x)
	{
		return query(x, 1, 0, sz(xv) - 1);
	}
};
 
 
 
 
 
 
 
 
 
 
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;
	}
 
	// if(Q > 40'000) assert(0);
 
 
	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;
 
		// cerr << "ypx : " << T[i]+A[i] << ' ' << (T[i] + abs(A[i] - B[i])) + B[i] << '\n';
		// cerr << "ymx : " << T[i] - A[i] << ' ' << (T[i] + abs(A[i] - B[i])) - B[i] << '\n';
	}
 
	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] ];
			}
		}
	}
 
 
 
 
 
	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]);
 
			// cerr << i << ' ' << j << " : " << dp[i][j] << '\n';
		}
	}
 
 
	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;
		}
 
		// cerr << plo << ' ' << mlo << " A \n";
 
		queries[plo][mlo].push_back(j);
	}
 
	// cerr << "done\n";


 
	// for(int pi = 1; pi <= pct; pi++)
	// {
	// 	cerr << ypx[pi] << " : ";
	// 	for(int mi = 1; mi <= mct; mi++)
	// 	{
	// 		cerr << dp[pi][mi] << ' ';
	// 	}
	// 	cerr << '\n';
	// }
 
 
 
 
	for(int mi = 1; mi <= mct; mi++)
	{

		// cerr << "\n\n\n\n\n\n\n\n\n\n";
		set<ll> xv;

		for(int pi = pct; pi >= 1; pi--)
		{
			for(int qr : queries[pi][mi])
			{
				xv.insert((ymx[mi] - (P[qr] - X[qr]))/2);
			}
		}

		vll xvv;

		for(ll kv : xv) xvv.push_back(kv);

		if(xvv.empty()) continue;

		// lct CHT(xvv, 0, sz(xvv) - 1);

		lct CHT(xvv);

		// for(ll xvi : xvv) cerr << "xvi = " << xvi << '\n';
 
		for(int pi = pct; pi >= 1; pi--)
		{
			// cerr << "\n\n\n\n\n";

			// cerr << "pi mi = " << pi << ' ' << mi << '\n';
 
			// if(mi == 3)
				// cerr << pi << ' ' << mi << " : " << "insert line " << ' ' << horiz_basic[pi][mi - 1] << ' ' << dp[pi][mi] << '\n';
 
 
			CHT.insert(horiz_basic[pi][mi - 1], dp[pi][mi]);

			// cerr << "inserting " << horiz_basic[pi][mi-1] << ' ' << dp[pi][mi] << '\n';
 
			for(int qr : queries[pi][mi])
			{
				res[qr] = max(res[qr], CHT.query((ymx[mi] - (P[qr] - X[qr]))/2));

				// cerr << "querying " << (ymx[mi] - (P[qr] - X[qr]))/2 << '\n';

				// cerr << qr << " -> " << res[qr] << '\n';
				// cerr << " ! " << res[qr] << '\n';
 
				// cerr << "query = " << qr << ' ' << pi << ' ' << mi << '\n';
				// cerr << "YMX = " << ymx[mi] << " - " << (P[qr] - X[qr]) << '\n';
				// cerr << (ymx[mi] - (P[qr] - X[qr]))/2 << '\n';
 
				// cerr << "x = " << (ymx[mi] - (P[qr] - X[qr]))/2 << "\n";
			}
		}
	}
 
	// cerr << pct << " ; " << mct << '\n';
 
 
	
 
 

 	// cerr << "----------------------------------\n";
 
 
	// cerr << "done 1\n";
 
	for(int pi = 1; pi <= pct; pi++)
	{
		// cerr << "\n\n\n\n\n\n\n\n\n\n";
		set<ll> xv;

		for(int mi = mct; mi >= 1; mi--)
		{
			for(int qr : queries[pi][mi])
			{
				xv.insert((ypx[pi] - (P[qr] + X[qr]))/2);
			}
		}

		vll xvv;

		for(ll kv : xv) xvv.push_back(kv);

		if(xvv.empty()) continue;








		lct CHT(xvv);
 
		for(int mi = mct; mi >= 1; mi--)
		{
 
 	// c
			CHT.insert(vert_basic[pi - 1][mi], dp[pi][mi]);
 
			// cerr << "ins done\n";

			// cerr << "inserting : " << vert_basic[pi - 1][mi] << ", " << dp[pi][mi] << '\n';
 
			for(int qr : queries[pi][mi])
			{
				// cerr << "\n\n\n";
				// cerr << "query = " << qr << " : " << pi << ' ' << mi << '\n';
				res[qr] = max(res[qr], CHT.query((ypx[pi] - (P[qr] + X[qr]))/2));

				// cerr << qr << " -> " << res[qr] << '\n';
				// cerr << " ! " << res[qr] << '\n';
 
				// cerr << "query done\n";

				// cerr << pi << ' ' << mi << ' ' << qr << '\n';

				// cerr << "query at " << CHT.query((ypx[pi] - (P[qr] + X[qr]))/2) << '\n';
			}
 
			// c
 
			// cerr << "finished\n";
		}
	}
 
 
	for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
 
 
}

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