oj.uz

답안 #529287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529287 2022-02-22T16:42:37 Z blue Bodyguard (JOI21_bodyguard) C++17
13 / 100
 6814 ms 1235208 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>;


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
{
	ll e;

	ll a;
	ll b;
};

bool operator < (slope_line A, slope_line B)
{
	return A.a < B.a;
}

struct point_line
{
	ll e;

	ll a;
	ll b;
};

bool operator < (point_line A, point_line B)
{
	return A.e < B.e;
}

ll get_intersect(ll a1, ll b1, ll a2, ll b2)
{
	return ll(b1 - b2) / ll(a2 - a1);
}


bool good(ll a0, ll b0, ll a, ll b, ll a1, ll b1)
{
	return ll(b0 - b) / ll(a - a0) < ll(b - b1) / ll(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({ll(x), 0, 0});

		if(it == pl.end()) while(1);


		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";

		// cerr << "check A\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;

				if(!good(a0, b0, a, b, a1, b1))
				{
					return;
				}
				// cerr << "passed\n";
			}
		}




		while(1)
		{
			// cerr << "check B1\n";
			nxt = sl.find({-1, a, b});
			nxt++;

			if(nxt == sl.end()) break;

			// cerr << "B2\n";

			nxt2 = nxt;
			nxt2++;

			if(nxt2 == sl.end()) break;

			// cerr << "B3\n";

			if(good(a, b, nxt->a, nxt->b, nxt2->a, nxt2->b)) break;

			// cerr << "hello\n";

			pl.erase({nxt->e, nxt->a, nxt->b});
			sl.erase(nxt);

			// cerr << "B4\n";
		}

		// cerr << "check C\n";

		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;
			ll prv2e = get_intersect(a, b, prv2->a, prv2->b);

			pl.erase({prv->e, prv->a, prv->b});
			sl.erase(prv);

			pl.erase({prv2->e, prv2->a, prv2->b});
			sl.erase(prv2);

			sl.insert({prv2e, prv2a, prv2b});
			pl.insert({prv2e, prv2a, prv2b});
		}


		ll endv, startv;

		// cerr << "check D\n";



		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 = ll(nxt->b - b) / ll(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 = ll(prv->b - b) / ll(a - prv->a);

			slope_line new_prev = {startv, prv->a, prv->b};


			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});
		}

		// cerr << "check E\n";


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

	// 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;
	}

	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++)
	{
		cht CHT;

		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 << " ! " << res[qr] << '\n';
			}
		}
	}

	// cerr << "done 1\n";

	for(int pi = 1; pi <= pct; pi++)
	{
		cht CHT;

		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

# 결과 실행 시간 메모리 Grader output
1 Correct 6302 ms 715272 KB Output is correct
2 Correct 6613 ms 724652 KB Output is correct
3 Correct 2200 ms 281480 KB Output is correct
4 Correct 873 ms 108696 KB Output is correct
5 Correct 6814 ms 1235208 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5991 ms 1153888 KB Output is correct
2 Correct 6005 ms 1153996 KB Output is correct
3 Correct 5785 ms 1138860 KB Output is correct
4 Correct 23 ms 48260 KB Output is correct
5 Correct 5712 ms 1154008 KB Output is correct
6 Correct 4147 ms 1153928 KB Output is correct
7 Correct 4073 ms 1152576 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5991 ms 1153888 KB Output is correct
2 Correct 6005 ms 1153996 KB Output is correct
3 Correct 5785 ms 1138860 KB Output is correct
4 Correct 23 ms 48260 KB Output is correct
5 Correct 5712 ms 1154008 KB Output is correct
6 Correct 4147 ms 1153928 KB Output is correct
7 Correct 4073 ms 1152576 KB Output is correct
8 Incorrect 5919 ms 1154032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5991 ms 1153888 KB Output is correct
2 Correct 6005 ms 1153996 KB Output is correct
3 Correct 5785 ms 1138860 KB Output is correct
4 Correct 23 ms 48260 KB Output is correct
5 Correct 5712 ms 1154008 KB Output is correct
6 Correct 4147 ms 1153928 KB Output is correct
7 Correct 4073 ms 1152576 KB Output is correct
8 Incorrect 5919 ms 1154032 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6302 ms 715272 KB Output is correct
2 Correct 6613 ms 724652 KB Output is correct
3 Correct 2200 ms 281480 KB Output is correct
4 Correct 873 ms 108696 KB Output is correct
5 Correct 6814 ms 1235208 KB Output is correct
6 Correct 5991 ms 1153888 KB Output is correct
7 Correct 6005 ms 1153996 KB Output is correct
8 Correct 5785 ms 1138860 KB Output is correct
9 Correct 23 ms 48260 KB Output is correct
10 Correct 5712 ms 1154008 KB Output is correct
11 Correct 4147 ms 1153928 KB Output is correct
12 Correct 4073 ms 1152576 KB Output is correct
13 Incorrect 5919 ms 1154032 KB Output isn't correct
14 Halted 0 ms 0 KB -