Submission #593492

#	Time	Username	Problem	Language	Result	Execution time	Memory
593492		cheissmart	Bodyguard (JOI21_bodyguard)	C++14	100 / 100	5843 ms	944200 KiB

bodyguard

#include <bits/stdc++.h>
#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;
const ll oo = 1e18;
const ll C = 4e9;

struct DS {
	struct line {
		ll m, b;
		line(ll _m = 0, ll _b = -oo) {
			m = _m, b = _b;
		} 
		ll operator() (ll x) {
			return m * x + b;
		}
	};
	struct node {
		node *l, *r;
		line f;
		node(line _f = line()) {
			l = r = nullptr;
			f = _f;
		}
	};
	node* root;
	DS() { root = nullptr; }
	void upd(node*& t, line f, ll tl = 0, ll tr = C) {
		if(!t) t = new node();
		ll tm = (tl + tr) / 2;
		if(f(tm) > t -> f(tm)) swap(f, t -> f);
		if(f(tl) > t -> f(tl)) upd(t -> l, f, tl, tm);
		if(f(tr - 1) > t -> f(tr - 1)) upd(t -> r, f, tm, tr);
	}
	void insert(ll m, ll b) {
		upd(root, line(m, b));
	}
	ll qry(node* t, ll x, ll tl = 0, ll tr = C) {
		if(!t) return -oo;
		ll tm = (tl + tr) / 2;
		ll ans = t -> f(x);
		if(x < tm) ans = max(ans, qry(t -> l, x, tl, tm));
		else ans = max(ans, qry(t -> r, x, tm, tr));
		return ans;
	}
	ll qry(ll x) {
		return qry(root, x);
	}
};

signed main()
{
	IO_OP;

	int n, q;
	cin >> n >> q;
	V<pair<pair<pair<ll, ll>, pair<ll, ll>>, int>> ev;
	V<ll> xs, ys;
	for(int i = 0; i < n; i++) {
		ll t, x, y, c, d;
		cin >> t >> x >> y >> c, d = abs(x - y);
		assert(c % 2 == 0);
		c /= 2;
		pair<ll, ll> a = {t + x, t - x};
		pair<ll, ll> 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);
	}
	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();
		assert((a.F == b.F || a.S == b.S) && a != b);
		if(a.F == b.F) {
			assert(a.S < b.S);
			for(int i = a.S; i < b.S; i++)
				dy[a.F][i] = max(dy[a.F][i], c);
		} else {
			assert(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] + dx[i][j] * (xs[i + 1] - xs[i]));
			if(j + 1 < SZ(ys)) dp[i][j] = max(dp[i][j], dp[i][j + 1] + dy[i][j] * (ys[j + 1] - ys[j]));
		}
	}

	V<V<V<pair<pair<ll, ll>, int>>>> qq(SZ(xs), V<V<pair<pair<ll, ll>, int>>>(SZ(ys)));
	V<ll> ans(q);
	for(int i = 0; i < q; i++) {
		ll t, x;
		cin >> t >> x;
		pair<ll, ll> 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 function 'int main()':
bodyguard.cpp:104:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |  for(auto[pab, c]:ev) {
      |          ^
bodyguard.cpp:105:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |   auto[a, b] = pab;
      |       ^
bodyguard.cpp:146:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |    for(auto[a, qi]:qq[i][j])
      |            ^
bodyguard.cpp:155:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |    for(auto[a, qi]:qq[i][j])
      |            ^

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