oj.uz

답안 #529516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529516 2022-02-23T05:51:13 Z blue Bodyguard (JOI21_bodyguard) C++17
13 / 100
 6739 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;
 
	lct* left = NULL;
	lct* right = NULL;

	lct(vll& xv, ll i, ll 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
		{
 
			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;
 
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 6739 ms 970772 KB Output is correct
2 Correct 6523 ms 977604 KB Output is correct
3 Correct 2530 ms 394160 KB Output is correct
4 Correct 1211 ms 118380 KB Output is correct
5 Correct 2136 ms 1234132 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 1156068 KB Output is correct
2 Correct 968 ms 1156956 KB Output is correct
3 Correct 924 ms 1138868 KB Output is correct
4 Correct 25 ms 48328 KB Output is correct
5 Correct 1002 ms 1153964 KB Output is correct
6 Correct 904 ms 1153972 KB Output is correct
7 Correct 1016 ms 1152604 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 1156068 KB Output is correct
2 Correct 968 ms 1156956 KB Output is correct
3 Correct 924 ms 1138868 KB Output is correct
4 Correct 25 ms 48328 KB Output is correct
5 Correct 1002 ms 1153964 KB Output is correct
6 Correct 904 ms 1153972 KB Output is correct
7 Correct 1016 ms 1152604 KB Output is correct
8 Runtime error 2523 ms 2097156 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 1156068 KB Output is correct
2 Correct 968 ms 1156956 KB Output is correct
3 Correct 924 ms 1138868 KB Output is correct
4 Correct 25 ms 48328 KB Output is correct
5 Correct 1002 ms 1153964 KB Output is correct
6 Correct 904 ms 1153972 KB Output is correct
7 Correct 1016 ms 1152604 KB Output is correct
8 Runtime error 2523 ms 2097156 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6739 ms 970772 KB Output is correct
2 Correct 6523 ms 977604 KB Output is correct
3 Correct 2530 ms 394160 KB Output is correct
4 Correct 1211 ms 118380 KB Output is correct
5 Correct 2136 ms 1234132 KB Output is correct
6 Correct 962 ms 1156068 KB Output is correct
7 Correct 968 ms 1156956 KB Output is correct
8 Correct 924 ms 1138868 KB Output is correct
9 Correct 25 ms 48328 KB Output is correct
10 Correct 1002 ms 1153964 KB Output is correct
11 Correct 904 ms 1153972 KB Output is correct
12 Correct 1016 ms 1152604 KB Output is correct
13 Runtime error 2523 ms 2097156 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -