oj.uz

Submission #529517

# Submission time Handle Problem Language Result Execution time Memory
529517 2022-02-23T05:56:21 Z blue Bodyguard (JOI21_bodyguard) C++17
48 / 100
 7507 ms 2097156 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);
	}
};
 
 
 
 
 
 
 
 
 
 
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 mi = 1; mi <= mct; mi++)
	{

		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, 0, sz(xvv) - 1);
 
		for(int pi = pct; pi >= 1; pi--)
		{
			// cerr << "\n\n\n\n\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]);
 
			for(int qr : queries[pi][mi])
			{
				res[qr] = max(res[qr], CHT.query((ymx[mi] - (P[qr] - X[qr]))/2));
				// 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';
 
 
 
	// for(int pi = 1; pi <= pct; pi++)
	// {
	// 	cerr << ypx[pi] << " : ";
	// 	for(int mi = 1; mi <= mct; mi++)
	// 	{
	// 		cerr << dp[pi][mi] << ' ';
	// 	}
	// 	cerr << '\n';
	// }
	
 
 
 
 
	// cerr << "done 1\n";
 
	for(int pi = 1; pi <= pct; pi++)
	{
		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, 0, sz(xvv) - 1);
 
		for(int mi = mct; mi >= 1; mi--)
		{
 
			// cerr << "pi mi = " << pi << ' ' << mi << '\n';
			CHT.insert(vert_basic[pi - 1][mi], dp[pi][mi]);
 
			// cerr << "ins done\n";
 
			for(int qr : queries[pi][mi])
			{
				// cerr << "query = " << qr << " : " << pi << ' ' << mi << '\n';
				res[qr] = max(res[qr], CHT.query((ypx[pi] - (P[qr] + X[qr]))/2));
				// cerr << " ! " << res[qr] << '\n';
 
				// cerr << "query done\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 4174 ms 719392 KB Output is correct
2 Correct 4650 ms 723348 KB Output is correct
3 Correct 1929 ms 279920 KB Output is correct
4 Correct 1198 ms 107088 KB Output is correct
5 Correct 2083 ms 1236096 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 1154000 KB Output is correct
2 Correct 970 ms 1154164 KB Output is correct
3 Correct 922 ms 1138988 KB Output is correct
4 Correct 24 ms 48332 KB Output is correct
5 Correct 970 ms 1153992 KB Output is correct
6 Correct 922 ms 1153972 KB Output is correct
7 Correct 1000 ms 1152660 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 1154000 KB Output is correct
2 Correct 970 ms 1154164 KB Output is correct
3 Correct 922 ms 1138988 KB Output is correct
4 Correct 24 ms 48332 KB Output is correct
5 Correct 970 ms 1153992 KB Output is correct
6 Correct 922 ms 1153972 KB Output is correct
7 Correct 1000 ms 1152660 KB Output is correct
8 Correct 1249 ms 1154480 KB Output is correct
9 Correct 1285 ms 1154624 KB Output is correct
10 Correct 1090 ms 1137396 KB Output is correct
11 Correct 25 ms 48528 KB Output is correct
12 Correct 1044 ms 1154324 KB Output is correct
13 Correct 1059 ms 1154712 KB Output is correct
14 Correct 985 ms 1155144 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 1154000 KB Output is correct
2 Correct 970 ms 1154164 KB Output is correct
3 Correct 922 ms 1138988 KB Output is correct
4 Correct 24 ms 48332 KB Output is correct
5 Correct 970 ms 1153992 KB Output is correct
6 Correct 922 ms 1153972 KB Output is correct
7 Correct 1000 ms 1152660 KB Output is correct
8 Correct 1249 ms 1154480 KB Output is correct
9 Correct 1285 ms 1154624 KB Output is correct
10 Correct 1090 ms 1137396 KB Output is correct
11 Correct 25 ms 48528 KB Output is correct
12 Correct 1044 ms 1154324 KB Output is correct
13 Correct 1059 ms 1154712 KB Output is correct
14 Correct 985 ms 1155144 KB Output is correct
15 Correct 1741 ms 1168512 KB Output is correct
16 Correct 1714 ms 1168644 KB Output is correct
17 Correct 1528 ms 1152004 KB Output is correct
18 Correct 39 ms 52820 KB Output is correct
19 Correct 1217 ms 1161676 KB Output is correct
20 Correct 1150 ms 1167936 KB Output is correct
21 Correct 1027 ms 1169988 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4174 ms 719392 KB Output is correct
2 Correct 4650 ms 723348 KB Output is correct
3 Correct 1929 ms 279920 KB Output is correct
4 Correct 1198 ms 107088 KB Output is correct
5 Correct 2083 ms 1236096 KB Output is correct
6 Correct 1403 ms 1154000 KB Output is correct
7 Correct 970 ms 1154164 KB Output is correct
8 Correct 922 ms 1138988 KB Output is correct
9 Correct 24 ms 48332 KB Output is correct
10 Correct 970 ms 1153992 KB Output is correct
11 Correct 922 ms 1153972 KB Output is correct
12 Correct 1000 ms 1152660 KB Output is correct
13 Correct 1249 ms 1154480 KB Output is correct
14 Correct 1285 ms 1154624 KB Output is correct
15 Correct 1090 ms 1137396 KB Output is correct
16 Correct 25 ms 48528 KB Output is correct
17 Correct 1044 ms 1154324 KB Output is correct
18 Correct 1059 ms 1154712 KB Output is correct
19 Correct 985 ms 1155144 KB Output is correct
20 Correct 1741 ms 1168512 KB Output is correct
21 Correct 1714 ms 1168644 KB Output is correct
22 Correct 1528 ms 1152004 KB Output is correct
23 Correct 39 ms 52820 KB Output is correct
24 Correct 1217 ms 1161676 KB Output is correct
25 Correct 1150 ms 1167936 KB Output is correct
26 Correct 1027 ms 1169988 KB Output is correct
27 Runtime error 7507 ms 2097156 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -