oj.uz

Submission #529546

# Submission time Handle Problem Language Result Execution time Memory
529546 2022-02-23T06:53:45 Z blue Bodyguard (JOI21_bodyguard) C++17
100 / 100
 10425 ms 1605076 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4813 ms 717076 KB Output is correct
2 Correct 5005 ms 724112 KB Output is correct
3 Correct 1967 ms 281272 KB Output is correct
4 Correct 1205 ms 108484 KB Output is correct
5 Correct 2122 ms 1239424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 1153880 KB Output is correct
2 Correct 968 ms 1154048 KB Output is correct
3 Correct 1046 ms 1138752 KB Output is correct
4 Correct 24 ms 48332 KB Output is correct
5 Correct 1060 ms 1153888 KB Output is correct
6 Correct 975 ms 1153900 KB Output is correct
7 Correct 1138 ms 1152480 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 1153880 KB Output is correct
2 Correct 968 ms 1154048 KB Output is correct
3 Correct 1046 ms 1138752 KB Output is correct
4 Correct 24 ms 48332 KB Output is correct
5 Correct 1060 ms 1153888 KB Output is correct
6 Correct 975 ms 1153900 KB Output is correct
7 Correct 1138 ms 1152480 KB Output is correct
8 Correct 1413 ms 1153952 KB Output is correct
9 Correct 1364 ms 1154232 KB Output is correct
10 Correct 1126 ms 1137080 KB Output is correct
11 Correct 30 ms 48580 KB Output is correct
12 Correct 1136 ms 1153984 KB Output is correct
13 Correct 1053 ms 1154020 KB Output is correct
14 Correct 974 ms 1154272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 1153880 KB Output is correct
2 Correct 968 ms 1154048 KB Output is correct
3 Correct 1046 ms 1138752 KB Output is correct
4 Correct 24 ms 48332 KB Output is correct
5 Correct 1060 ms 1153888 KB Output is correct
6 Correct 975 ms 1153900 KB Output is correct
7 Correct 1138 ms 1152480 KB Output is correct
8 Correct 1413 ms 1153952 KB Output is correct
9 Correct 1364 ms 1154232 KB Output is correct
10 Correct 1126 ms 1137080 KB Output is correct
11 Correct 30 ms 48580 KB Output is correct
12 Correct 1136 ms 1153984 KB Output is correct
13 Correct 1053 ms 1154020 KB Output is correct
14 Correct 974 ms 1154272 KB Output is correct
15 Correct 1902 ms 1157076 KB Output is correct
16 Correct 1906 ms 1157168 KB Output is correct
17 Correct 2043 ms 1144896 KB Output is correct
18 Correct 37 ms 50392 KB Output is correct
19 Correct 1336 ms 1155660 KB Output is correct
20 Correct 1233 ms 1155780 KB Output is correct
21 Correct 1004 ms 1160000 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4813 ms 717076 KB Output is correct
2 Correct 5005 ms 724112 KB Output is correct
3 Correct 1967 ms 281272 KB Output is correct
4 Correct 1205 ms 108484 KB Output is correct
5 Correct 2122 ms 1239424 KB Output is correct
6 Correct 998 ms 1153880 KB Output is correct
7 Correct 968 ms 1154048 KB Output is correct
8 Correct 1046 ms 1138752 KB Output is correct
9 Correct 24 ms 48332 KB Output is correct
10 Correct 1060 ms 1153888 KB Output is correct
11 Correct 975 ms 1153900 KB Output is correct
12 Correct 1138 ms 1152480 KB Output is correct
13 Correct 1413 ms 1153952 KB Output is correct
14 Correct 1364 ms 1154232 KB Output is correct
15 Correct 1126 ms 1137080 KB Output is correct
16 Correct 30 ms 48580 KB Output is correct
17 Correct 1136 ms 1153984 KB Output is correct
18 Correct 1053 ms 1154020 KB Output is correct
19 Correct 974 ms 1154272 KB Output is correct
20 Correct 1902 ms 1157076 KB Output is correct
21 Correct 1906 ms 1157168 KB Output is correct
22 Correct 2043 ms 1144896 KB Output is correct
23 Correct 37 ms 50392 KB Output is correct
24 Correct 1336 ms 1155660 KB Output is correct
25 Correct 1233 ms 1155780 KB Output is correct
26 Correct 1004 ms 1160000 KB Output is correct
27 Correct 7693 ms 1360392 KB Output is correct
28 Correct 7549 ms 1360092 KB Output is correct
29 Correct 7325 ms 1479592 KB Output is correct
30 Correct 1813 ms 207180 KB Output is correct
31 Correct 3268 ms 1233056 KB Output is correct
32 Correct 3812 ms 1285580 KB Output is correct
33 Correct 10425 ms 1605076 KB Output is correct