oj.uz

Submission #593492

# Submission time Handle Problem Language Result Execution time Memory
593492 2022-07-11T09:11:13 Z cheissmart Bodyguard (JOI21_bodyguard) C++14
100 / 100
 5843 ms 944200 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5411 ms 513572 KB Output is correct
2 Correct 5341 ms 517300 KB Output is correct
3 Correct 1817 ms 220936 KB Output is correct
4 Correct 968 ms 101444 KB Output is correct
5 Correct 3450 ms 837132 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2340 ms 702908 KB Output is correct
2 Correct 2289 ms 703376 KB Output is correct
3 Correct 2484 ms 693860 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2016 ms 784500 KB Output is correct
6 Correct 2165 ms 738792 KB Output is correct
7 Correct 1356 ms 691156 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2340 ms 702908 KB Output is correct
2 Correct 2289 ms 703376 KB Output is correct
3 Correct 2484 ms 693860 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2016 ms 784500 KB Output is correct
6 Correct 2165 ms 738792 KB Output is correct
7 Correct 1356 ms 691156 KB Output is correct
8 Correct 2267 ms 703220 KB Output is correct
9 Correct 2315 ms 703220 KB Output is correct
10 Correct 2435 ms 692432 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 2136 ms 784696 KB Output is correct
13 Correct 2245 ms 738936 KB Output is correct
14 Correct 2743 ms 701644 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2340 ms 702908 KB Output is correct
2 Correct 2289 ms 703376 KB Output is correct
3 Correct 2484 ms 693860 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2016 ms 784500 KB Output is correct
6 Correct 2165 ms 738792 KB Output is correct
7 Correct 1356 ms 691156 KB Output is correct
8 Correct 2267 ms 703220 KB Output is correct
9 Correct 2315 ms 703220 KB Output is correct
10 Correct 2435 ms 692432 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 2136 ms 784696 KB Output is correct
13 Correct 2245 ms 738936 KB Output is correct
14 Correct 2743 ms 701644 KB Output is correct
15 Correct 2353 ms 706464 KB Output is correct
16 Correct 2360 ms 706400 KB Output is correct
17 Correct 2488 ms 697008 KB Output is correct
18 Correct 15 ms 2892 KB Output is correct
19 Correct 2064 ms 787208 KB Output is correct
20 Correct 2208 ms 741516 KB Output is correct
21 Correct 2786 ms 703096 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5411 ms 513572 KB Output is correct
2 Correct 5341 ms 517300 KB Output is correct
3 Correct 1817 ms 220936 KB Output is correct
4 Correct 968 ms 101444 KB Output is correct
5 Correct 3450 ms 837132 KB Output is correct
6 Correct 2340 ms 702908 KB Output is correct
7 Correct 2289 ms 703376 KB Output is correct
8 Correct 2484 ms 693860 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 2016 ms 784500 KB Output is correct
11 Correct 2165 ms 738792 KB Output is correct
12 Correct 1356 ms 691156 KB Output is correct
13 Correct 2267 ms 703220 KB Output is correct
14 Correct 2315 ms 703220 KB Output is correct
15 Correct 2435 ms 692432 KB Output is correct
16 Correct 4 ms 1364 KB Output is correct
17 Correct 2136 ms 784696 KB Output is correct
18 Correct 2245 ms 738936 KB Output is correct
19 Correct 2743 ms 701644 KB Output is correct
20 Correct 2353 ms 706464 KB Output is correct
21 Correct 2360 ms 706400 KB Output is correct
22 Correct 2488 ms 697008 KB Output is correct
23 Correct 15 ms 2892 KB Output is correct
24 Correct 2064 ms 787208 KB Output is correct
25 Correct 2208 ms 741516 KB Output is correct
26 Correct 2786 ms 703096 KB Output is correct
27 Correct 5843 ms 938624 KB Output is correct
28 Correct 5838 ms 935040 KB Output is correct
29 Correct 4065 ms 884548 KB Output is correct
30 Correct 893 ms 120100 KB Output is correct
31 Correct 3252 ms 905460 KB Output is correct
32 Correct 4313 ms 944200 KB Output is correct
33 Correct 3695 ms 874076 KB Output is correct