oj.uz

Submission #529453

# Submission time Handle Problem Language Result Execution time Memory
529453 2022-02-23T03:17:37 Z blue Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 1157460 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
{
	double e;
 
	ll a;
	ll b;
};
 
bool operator < (slope_line A, slope_line B)
{
	return A.a < B.a;
}
 
struct point_line
{
	double 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 double(b1 - b2) / double(a2 - a1);
}
 
 
bool good(ll a0, ll b0, ll a, ll b, ll a1, ll b1)
{
	return double(b0 - b) / double(a - a0) < double(b - b1) / double(a1 - a);
}
 
 
struct cht
{	
	multiset<slope_line> sl;
	multiset<point_line> pl;
 
	ll query(ll x)
	{
		ll res = 0;

		for(auto& z : sl) res = max(res, z.a * x  + z.b);

		return res;
	}
 
	void insert(ll a, ll b)
	{
		// cerr << "inserting " << a << ' ' << b << '\n';
		sl.insert({-1, a, b});
	}
};
 
 
 
 
 
 
 
 
 
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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25107 ms 674544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5577 ms 1154096 KB Output is correct
2 Correct 5566 ms 1154276 KB Output is correct
3 Correct 5677 ms 1138988 KB Output is correct
4 Correct 24 ms 48460 KB Output is correct
5 Correct 5423 ms 1154104 KB Output is correct
6 Correct 5500 ms 1154104 KB Output is correct
7 Correct 5199 ms 1152696 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5577 ms 1154096 KB Output is correct
2 Correct 5566 ms 1154276 KB Output is correct
3 Correct 5677 ms 1138988 KB Output is correct
4 Correct 24 ms 48460 KB Output is correct
5 Correct 5423 ms 1154104 KB Output is correct
6 Correct 5500 ms 1154104 KB Output is correct
7 Correct 5199 ms 1152696 KB Output is correct
8 Correct 5484 ms 1154216 KB Output is correct
9 Correct 5495 ms 1154552 KB Output is correct
10 Correct 5234 ms 1137168 KB Output is correct
11 Correct 47 ms 48708 KB Output is correct
12 Correct 5356 ms 1154284 KB Output is correct
13 Correct 5331 ms 1154272 KB Output is correct
14 Correct 5476 ms 1154308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5577 ms 1154096 KB Output is correct
2 Correct 5566 ms 1154276 KB Output is correct
3 Correct 5677 ms 1138988 KB Output is correct
4 Correct 24 ms 48460 KB Output is correct
5 Correct 5423 ms 1154104 KB Output is correct
6 Correct 5500 ms 1154104 KB Output is correct
7 Correct 5199 ms 1152696 KB Output is correct
8 Correct 5484 ms 1154216 KB Output is correct
9 Correct 5495 ms 1154552 KB Output is correct
10 Correct 5234 ms 1137168 KB Output is correct
11 Correct 47 ms 48708 KB Output is correct
12 Correct 5356 ms 1154284 KB Output is correct
13 Correct 5331 ms 1154272 KB Output is correct
14 Correct 5476 ms 1154308 KB Output is correct
15 Correct 7255 ms 1157316 KB Output is correct
16 Correct 6884 ms 1157460 KB Output is correct
17 Correct 5982 ms 1142580 KB Output is correct
18 Correct 121 ms 50112 KB Output is correct
19 Correct 6961 ms 1155752 KB Output is correct
20 Correct 7517 ms 1155792 KB Output is correct
21 Correct 7743 ms 1155600 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25107 ms 674544 KB Time limit exceeded
2 Halted 0 ms 0 KB -