oj.uz

Submission #530220

# Submission time Handle Problem Language Result Execution time Memory
530220 2022-02-24T19:56:53 Z blue Bodyguard (JOI21_bodyguard) C++17
100 / 100
 14700 ms 1578272 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);

bool dbg = 0;
 
 
 
 
const ll INF = 1'000'000'000'000'000'000LL;
 
 
 
 
struct lct
{
	vll xv;
 
	// vector<bool> good;
	vector<ll> a;
	vector<ll> b;
 
	lct(vll& xv_)
	{
		// if(dbg)
		// {
		// 	// cerr << "creating LCT : ";
		// 	// for(ll xv__ : xv_) cerr << xv__ << ' ';
		// 	// 	cerr << '\n';
		// }

		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(dbg)cerr << "insert line " << na << ' ' << nb << " : " << 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]) return;
 
		if(na * xv[xi] + nb >= a[i] * xv[xi] + b[i] && na * xv[xj] + nb >= a[i] * xv[xj] + b[i]) 
		{
			// if(dbg)
				// cerr << "direct\n";
			a[i] = na;
			b[i] = nb;
			// good[i] = 1;
 
		}
		else
		{
			// if(good[i])
			// 	insert(a[i], b[i], 2*i, xi, (xi+xj)/2);
			// insert(na, nb, 2*i, xi, (xi+xj)/2);
			
 
			// if(good[i])
			// 	insert(a[i], b[i], 2*i+1, (xi+xj)/2, xj);
			// insert(na, nb, 2*i+1, (xi+xj)/2+1, xj);
 
			// good[i] = 0;

			// if(dbg) cerr << na * xv[xi] + nb << " --- " << a[i] * xv[xi] + b[i] << '\n';
			// if(dbg) cerr << na * xv[xi] + nb - (a[i] * xv[xi] + b[i]) << '\n';
			// if(dbg) cerr << na * xv[xi] + nb - (a[i] * xv[xi] + b[i]) << ' ' << 0 << " : " << int(na * xv[xi] + nb - (a[i] * xv[xi] + b[i]) >= 0) << '\n';

			if(na * xv[xi] + nb >= a[i] * xv[xi] + b[i])
			{
				// cerr << "!!! " << na * xv[xi] + nb << ' ' << a[i] + xv[xi]

				if(na * xv[(xi+xj)/2] + nb >= a[i] * xv[(xi+xj)/2] + b[i])
				{
					// if(dbg)cerr << "Case A\n";
					insert(a[i], b[i], 2*i+1, (xi+xj)/2+1, xj);
					a[i] = na;
					b[i] = nb;
				}
				else
				{
					// if(dbg)cerr << "case B\n";
					insert(na, nb, 2*i, xi, (xi+xj)/2);
				}
			}
			else
			{
				if(na * xv[(xi+xj)/2 + 1] + nb >= a[i] * xv[(xi + xj) / 2 + 1] + b[i])
				{
					// if(dbg)cerr << "case C\n";
					insert(a[i], b[i], 2*i, xi, (xi+xj)/2);
					a[i] = na;
					b[i] = nb;
				}
				else
				{
					// if(dbg)cerr << "case D\n";
					insert(na, nb, 2*i + 1, (xi+xj)/2 + 1, xj);
				}
			}
		}
	}
 
	void insert(ll na, ll nb)
	{
		// if(dbg)cerr << "\n\n\n xv size = " << sz(xv) << '\n';
		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 cr = a[i] * x + b[i];

		if(xi != xj)
		{
			if(x <= xv[(xi+xj)/2]) cr = max(cr, query(x, 2*i, xi, (xi+xj)/2));
			else cr = max(cr, query(x, 2*i+1, (xi+xj)/2+1, xj));
		}

		return cr;
	}
 
	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;

		// cerr << "query " << j << " : " << (P[j]+X[j])/2 << '\n';
	}
 
	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);


		// cerr << "ypx : " << z.first / 2 << '\n';
	}
 
	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]];
	}
 
	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++)
			{
				horiz_basic[ start_ypx[i] ][j] = max(horiz_basic[ start_ypx[i] ][j], C[i]);
			
				horiz[start_ypx[i]][j] = horiz_basic[start_ypx[i]][j] * (ymx[j+1] - ymx[j]) / 2;
 
			}
		}
		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]);
 
		}
	}
 
 
	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 << j << " <> " << plo << ' ' << ypx[plo]/2 << '\n';
  
		queries[plo][mlo].push_back(j);
	}
	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);
 
 
		for(int pi = pct; pi >= 1; pi--)
		{
			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 << qr << " : " << pi << ' ' << mi << '\n';
			}
		}
	}


	// cerr << pct << ' ' << mct << '\n';

	for(int pi = 1; pi <= pct; pi++)
	{
		// cerr << "\n\n\n\n pi = " << pi << '\n'; 
		// if(pi == 3) dbg = 1;
		// else dbg = 0;
		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);

				// if(pi == 3) cerr << "query query " << qr << '\n';
			}
		}
 
		vll xvv;
 
		for(ll kv : xv) xvv.push_back(kv);
 
		if(xvv.empty()) continue;
 
		lct CHT(xvv);
 
		for(int mi = mct; mi >= 1; mi--)
		{
			// if(pi == 3) cerr << "add line " << vert_basic[pi - 1][mi] << ' ' << dp[pi][mi] << '\n';
			CHT.insert(vert_basic[pi - 1][mi], dp[pi][mi]);
 
			for(int qr : queries[pi][mi])
			{
				res[qr] = max(res[qr], CHT.query((ypx[pi] - (P[qr] + X[qr]))/2));
				// if(pi == 3) cerr << "query = " << qr << " : " << "x = " << (ypx[pi] - (P[qr] + X[qr]))/2 << '\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 4517 ms 715212 KB Output is correct
2 Correct 4345 ms 723044 KB Output is correct
3 Correct 2194 ms 280140 KB Output is correct
4 Correct 1436 ms 107300 KB Output is correct
5 Correct 2556 ms 1234184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 1153880 KB Output is correct
2 Correct 914 ms 1154044 KB Output is correct
3 Correct 879 ms 1138912 KB Output is correct
4 Correct 22 ms 48332 KB Output is correct
5 Correct 972 ms 1153844 KB Output is correct
6 Correct 909 ms 1153900 KB Output is correct
7 Correct 973 ms 1152456 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 1153880 KB Output is correct
2 Correct 914 ms 1154044 KB Output is correct
3 Correct 879 ms 1138912 KB Output is correct
4 Correct 22 ms 48332 KB Output is correct
5 Correct 972 ms 1153844 KB Output is correct
6 Correct 909 ms 1153900 KB Output is correct
7 Correct 973 ms 1152456 KB Output is correct
8 Correct 1447 ms 1153956 KB Output is correct
9 Correct 1278 ms 1154212 KB Output is correct
10 Correct 1067 ms 1137180 KB Output is correct
11 Correct 25 ms 48580 KB Output is correct
12 Correct 1053 ms 1154168 KB Output is correct
13 Correct 1040 ms 1154024 KB Output is correct
14 Correct 958 ms 1154252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 1153880 KB Output is correct
2 Correct 914 ms 1154044 KB Output is correct
3 Correct 879 ms 1138912 KB Output is correct
4 Correct 22 ms 48332 KB Output is correct
5 Correct 972 ms 1153844 KB Output is correct
6 Correct 909 ms 1153900 KB Output is correct
7 Correct 973 ms 1152456 KB Output is correct
8 Correct 1447 ms 1153956 KB Output is correct
9 Correct 1278 ms 1154212 KB Output is correct
10 Correct 1067 ms 1137180 KB Output is correct
11 Correct 25 ms 48580 KB Output is correct
12 Correct 1053 ms 1154168 KB Output is correct
13 Correct 1040 ms 1154024 KB Output is correct
14 Correct 958 ms 1154252 KB Output is correct
15 Correct 1743 ms 1157200 KB Output is correct
16 Correct 1756 ms 1157192 KB Output is correct
17 Correct 1486 ms 1144900 KB Output is correct
18 Correct 39 ms 50456 KB Output is correct
19 Correct 1104 ms 1155512 KB Output is correct
20 Correct 1118 ms 1155580 KB Output is correct
21 Correct 988 ms 1159960 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4517 ms 715212 KB Output is correct
2 Correct 4345 ms 723044 KB Output is correct
3 Correct 2194 ms 280140 KB Output is correct
4 Correct 1436 ms 107300 KB Output is correct
5 Correct 2556 ms 1234184 KB Output is correct
6 Correct 900 ms 1153880 KB Output is correct
7 Correct 914 ms 1154044 KB Output is correct
8 Correct 879 ms 1138912 KB Output is correct
9 Correct 22 ms 48332 KB Output is correct
10 Correct 972 ms 1153844 KB Output is correct
11 Correct 909 ms 1153900 KB Output is correct
12 Correct 973 ms 1152456 KB Output is correct
13 Correct 1447 ms 1153956 KB Output is correct
14 Correct 1278 ms 1154212 KB Output is correct
15 Correct 1067 ms 1137180 KB Output is correct
16 Correct 25 ms 48580 KB Output is correct
17 Correct 1053 ms 1154168 KB Output is correct
18 Correct 1040 ms 1154024 KB Output is correct
19 Correct 958 ms 1154252 KB Output is correct
20 Correct 1743 ms 1157200 KB Output is correct
21 Correct 1756 ms 1157192 KB Output is correct
22 Correct 1486 ms 1144900 KB Output is correct
23 Correct 39 ms 50456 KB Output is correct
24 Correct 1104 ms 1155512 KB Output is correct
25 Correct 1118 ms 1155580 KB Output is correct
26 Correct 988 ms 1159960 KB Output is correct
27 Correct 7868 ms 1309064 KB Output is correct
28 Correct 7828 ms 1308468 KB Output is correct
29 Correct 8108 ms 1428148 KB Output is correct
30 Correct 2285 ms 155360 KB Output is correct
31 Correct 2740 ms 1205916 KB Output is correct
32 Correct 3910 ms 1249016 KB Output is correct
33 Correct 14700 ms 1578272 KB Output is correct