oj.uz

Submission #529551

# Submission time Handle Problem Language Result Execution time Memory
529551 2022-02-23T07:04:29 Z blue Bodyguard (JOI21_bodyguard) C++17
100 / 100
 10616 ms 1580936 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
{
	vll xv;
 
	vector<bool> good;
	vector<ll> a;
	vector<ll> b;
 
	lct(vll& xv_)
	{
		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(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]) 
		{
 
			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;
		}
	}
 
	void insert(ll na, ll nb)
	{
		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 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;
	}
 
	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]];
	}
 
	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;
		}
 
		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));
			}
		}
	}
	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);
 
		for(int mi = mct; mi >= 1; mi--)
		{
			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));
			}
		}
	}
	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 4835 ms 715660 KB Output is correct
2 Correct 4573 ms 720824 KB Output is correct
3 Correct 2093 ms 277912 KB Output is correct
4 Correct 1243 ms 105096 KB Output is correct
5 Correct 2124 ms 1231892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 1153888 KB Output is correct
2 Correct 973 ms 1154060 KB Output is correct
3 Correct 967 ms 1138856 KB Output is correct
4 Correct 23 ms 48332 KB Output is correct
5 Correct 1125 ms 1153956 KB Output is correct
6 Correct 972 ms 1153968 KB Output is correct
7 Correct 1072 ms 1152532 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 1153888 KB Output is correct
2 Correct 973 ms 1154060 KB Output is correct
3 Correct 967 ms 1138856 KB Output is correct
4 Correct 23 ms 48332 KB Output is correct
5 Correct 1125 ms 1153956 KB Output is correct
6 Correct 972 ms 1153968 KB Output is correct
7 Correct 1072 ms 1152532 KB Output is correct
8 Correct 1318 ms 1154236 KB Output is correct
9 Correct 1418 ms 1154224 KB Output is correct
10 Correct 1191 ms 1137060 KB Output is correct
11 Correct 25 ms 48524 KB Output is correct
12 Correct 1056 ms 1154020 KB Output is correct
13 Correct 1083 ms 1154244 KB Output is correct
14 Correct 984 ms 1154244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 1153888 KB Output is correct
2 Correct 973 ms 1154060 KB Output is correct
3 Correct 967 ms 1138856 KB Output is correct
4 Correct 23 ms 48332 KB Output is correct
5 Correct 1125 ms 1153956 KB Output is correct
6 Correct 972 ms 1153968 KB Output is correct
7 Correct 1072 ms 1152532 KB Output is correct
8 Correct 1318 ms 1154236 KB Output is correct
9 Correct 1418 ms 1154224 KB Output is correct
10 Correct 1191 ms 1137060 KB Output is correct
11 Correct 25 ms 48524 KB Output is correct
12 Correct 1056 ms 1154020 KB Output is correct
13 Correct 1083 ms 1154244 KB Output is correct
14 Correct 984 ms 1154244 KB Output is correct
15 Correct 1932 ms 1156420 KB Output is correct
16 Correct 1894 ms 1156520 KB Output is correct
17 Correct 1614 ms 1144292 KB Output is correct
18 Correct 50 ms 49752 KB Output is correct
19 Correct 1422 ms 1155120 KB Output is correct
20 Correct 1187 ms 1155176 KB Output is correct
21 Correct 1020 ms 1159732 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4835 ms 715660 KB Output is correct
2 Correct 4573 ms 720824 KB Output is correct
3 Correct 2093 ms 277912 KB Output is correct
4 Correct 1243 ms 105096 KB Output is correct
5 Correct 2124 ms 1231892 KB Output is correct
6 Correct 958 ms 1153888 KB Output is correct
7 Correct 973 ms 1154060 KB Output is correct
8 Correct 967 ms 1138856 KB Output is correct
9 Correct 23 ms 48332 KB Output is correct
10 Correct 1125 ms 1153956 KB Output is correct
11 Correct 972 ms 1153968 KB Output is correct
12 Correct 1072 ms 1152532 KB Output is correct
13 Correct 1318 ms 1154236 KB Output is correct
14 Correct 1418 ms 1154224 KB Output is correct
15 Correct 1191 ms 1137060 KB Output is correct
16 Correct 25 ms 48524 KB Output is correct
17 Correct 1056 ms 1154020 KB Output is correct
18 Correct 1083 ms 1154244 KB Output is correct
19 Correct 984 ms 1154244 KB Output is correct
20 Correct 1932 ms 1156420 KB Output is correct
21 Correct 1894 ms 1156520 KB Output is correct
22 Correct 1614 ms 1144292 KB Output is correct
23 Correct 50 ms 49752 KB Output is correct
24 Correct 1422 ms 1155120 KB Output is correct
25 Correct 1187 ms 1155176 KB Output is correct
26 Correct 1020 ms 1159732 KB Output is correct
27 Correct 7586 ms 1313804 KB Output is correct
28 Correct 8010 ms 1313304 KB Output is correct
29 Correct 6905 ms 1433004 KB Output is correct
30 Correct 1861 ms 160656 KB Output is correct
31 Correct 3295 ms 1207912 KB Output is correct
32 Correct 3813 ms 1253024 KB Output is correct
33 Correct 10616 ms 1580936 KB Output is correct