Submission #593448

#	Time	Username	Problem	Language	Result	Execution time	Memory
593448		cheissmart	Bodyguard (JOI21_bodyguard)	C++14	42 / 100	25106 ms	951972 KiB

bodyguard

#include <bits/stdc++.h>
#define int ll
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

struct DS {
	V<pair<ll, ll>> tt;
	void insert(ll m, ll b) {
		tt.EB(m, b);
	}
	ll qry(ll x) {
		ll mx = 0;
		for(auto[m, b]:tt) {
			mx = max(mx, m * x + b);
		}
		return mx;
	}
};

void claim(bool b) {
	if(!b) while(1);
}

signed main()
{
	IO_OP;

	int n, q;
	cin >> n >> q;
	V<pair<pair<pi, pi>, int>> ev;
	vi xs, ys;
	for(int i = 0; i < n; i++) {
		int t, x, y, c, d;
		cin >> t >> x >> y >> c, d = abs(x - y);
		claim(c % 2 == 0);
		c /= 2;
		pi a = {t + x, t - x};
		pi b = {t + d + y, t + d - y};
		ev.EB(MP(a, b), c);
		xs.PB(a.F), ys.PB(a.S);
		xs.PB(b.F), ys.PB(b.S);

		assert((a.F == b.F || a.S == b.S) && a != b);
		if(a.F == b.F) {
			assert(a.S < b.S);
		} else {
			assert(a.F < b.F);
		}
	}
	sort(ALL(xs)), xs.resize(unique(ALL(xs)) - xs.begin());
	sort(ALL(ys)), ys.resize(unique(ALL(ys)) - ys.begin());

	V<vi> dx, dy;
	dx = dy = V<vi>(SZ(xs), vi(SZ(ys)));
	V<V<ll>> dp = V<V<ll>>(SZ(xs), V<ll>(SZ(ys)));

	for(auto[pab, c]:ev) {
		auto[a, b] = pab;
		a.F = lower_bound(ALL(xs), a.F) - xs.begin();
		a.S = lower_bound(ALL(ys), a.S) - ys.begin();
		b.F = lower_bound(ALL(xs), b.F) - xs.begin();
		b.S = lower_bound(ALL(ys), b.S) - ys.begin();
		claim((a.F == b.F || a.S == b.S) && a != b);
		if(a.F == b.F) {
			claim(a.S < b.S);
			for(int i = a.S; i < b.S; i++)
				dy[a.F][i] = max(dy[a.F][i], c);
		} else {
			claim(a.F < b.F);
			for(int i = a.F; i < b.F; i++)
				dx[i][a.S] = max(dx[i][a.S], c);
		}
	}

	for(int i = SZ(xs) - 1; i >= 0; i--) {
		for(int j = SZ(ys) - 1; j >= 0; j--) {
			if(i + 1 < SZ(xs)) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1LL * dx[i][j] * (xs[i + 1] - xs[i]));
			if(j + 1 < SZ(ys)) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1LL * dy[i][j] * (ys[j + 1] - ys[j]));
		}
	}

	V<V<V<pair<pi, int>>>> qq(SZ(xs), V<V<pair<pi, int>>>(SZ(ys)));
	V<ll> ans(q);
	for(int i = 0; i < q; i++) {
		int t, x;
		cin >> t >> x;
		pi a = {t + x, t - x};
		int he = lower_bound(ALL(xs), a.F) - xs.begin();
		int be = lower_bound(ALL(ys), a.S) - ys.begin();
		if(he < SZ(xs) && be < SZ(ys)) {
			qq[he][be].EB(a, i);
		}
	}
	for(int j = 0; j < SZ(ys); j++) {
		DS ds;
		for(int i = SZ(xs) - 1; i >= 0; i--) {
			int c = j ? dy[i][j - 1] : 0;
			ds.insert(c, dp[i][j]);
			for(auto[a, qi]:qq[i][j])
				ans[qi] = max(ans[qi], ds.qry(ys[j] - a.S));
		}
	}
	for(int i = 0; i < SZ(xs); i++) {
		DS ds;
		for(int j = SZ(ys) - 1; j >= 0; j--) {
			int c = i ? dx[i - 1][j] : 0;
			ds.insert(c, dp[i][j]);
			for(auto[a, qi]:qq[i][j])
				ans[qi] = max(ans[qi], ds.qry(xs[i] - a.F));
		}
	}

	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

bodyguard.cpp: In member function 'll DS::qry(ll)':
bodyguard.cpp:41:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   for(auto[m, b]:tt) {
      |           ^
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:85:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |  for(auto[pab, c]:ev) {
      |          ^
bodyguard.cpp:86:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |   auto[a, b] = pab;
      |       ^
bodyguard.cpp:127:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |    for(auto[a, qi]:qq[i][j])
      |            ^
bodyguard.cpp:136:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |    for(auto[a, qi]:qq[i][j])
      |            ^

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 52