oj.uz

Submission #892683

# Submission time Handle Problem Language Result Execution time Memory
892683 2023-12-25T16:50:06 Z marvinthang Bodyguard (JOI21_bodyguard) C++17
100 / 100
 4520 ms 915512 KB 
/*************************************
*    author: marvinthang             *
*    created: 25.12.2023 20:42:18    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

const long long INF = 1e18;

struct Line {
    long long a, b;
    Line(long long a = 0, long long b = INF): a(a), b(b) {}
    long long eval(long long x) { return a * x + b; }
};
struct ConvexHullTrick {
    vector <Line> lines;
    bool bad(Line a, Line b, Line c) { return (long double) (c.b - a.b) / (a.a - c.a) > (long double) (b.b - a.b) / (a.a - b.a); }
    void addLine(long long a, long long b) {
        Line l(a, b);
        while (!lines.empty() && lines.back().a <= l.a) lines.pop_back();
        while (lines.size() >= 2 && bad(lines.end()[-2], lines.back(), l)) lines.pop_back();
        lines.push_back(l);
    }
    void clear(void) {
    	lines.clear();
    }
    long long getMax(long long x) {
    	if (lines.empty()) return 0;
    	long long res = 0;
        int l = 0, r = (int) lines.size() - 2;
        while (l <= r) {
        	int m = (l + r) >> 1;
        	long long cur_1 = lines[m].eval(x);
        	long long cur_2 = lines[m + 1].eval(x);
        	maximize(res, max(cur_1, cur_2));
        	if (cur_1 < cur_2) l = m + 2;
        	else r = m - 1;
        }
        maximize(res, lines[r + 1].eval(x));
        return res;
    }
};
using CHT = ConvexHullTrick;

// end of template

void process(void) {
	int n, q; cin >> n >> q;
	vector <long long> x(n), y(n), u(n), v(n), c(n);
	vector <long long> cx, cy;
	REP(i, n) {
		long long t, a, b;
		cin >> t >> a >> b >> c[i]; c[i] /= 2;
		x[i] = t + a; 
		y[i] = t - a;
		u[i] = t + abs(a - b) + b;
		v[i] = t + abs(a - b) - b;
		cx.push_back(x[i]); cx.push_back(u[i]);
		cy.push_back(y[i]); cy.push_back(v[i]);
	}
	sort(ALL(cx)); cx.erase(unique(ALL(cx)), cx.end());
	sort(ALL(cy)); cy.erase(unique(ALL(cy)), cy.end());

	vector max_hor(cx.size(), vector<int>(cy.size()));
	vector max_ver(cx.size(), vector<int>(cy.size()));
	vector dp(cx.size(), vector<long long>(cy.size()));
	REP(i, n) {
		x[i] = lower_bound(ALL(cx), x[i]) - cx.begin();
		y[i] = lower_bound(ALL(cy), y[i]) - cy.begin();
		u[i] = lower_bound(ALL(cx), u[i]) - cx.begin();
		v[i] = lower_bound(ALL(cy), v[i]) - cy.begin();
		if (x[i] == u[i]) {
			FOR(p, y[i], v[i]) maximize(max_ver[x[i]][p], c[i]);
		} else {
			FOR(p, x[i], u[i]) maximize(max_hor[p][y[i]], c[i]);
		}
	}

	REPD(x, cx.size()) REPD(y, cy.size()) {
		if (y + 1 < (int) cy.size()) maximize(dp[x][y], dp[x][y + 1] + 1LL * (cy[y + 1] - cy[y]) * max_ver[x][y]);
		if (x + 1 < (int) cx.size()) maximize(dp[x][y], dp[x + 1][y] + 1LL * (cx[x + 1] - cx[x]) * max_hor[x][y]);
	}

	vector queriesAt(cx.size(), vector(cy.size(), vector<int>()));
	vector <long long> s(q), t(q);
	REP(i, q) {
		long long p, q; cin >> p >> q; 
		s[i] = p + q; t[i] = p - q;
		int u = lower_bound(ALL(cx), s[i]) - cx.begin();
		int v = lower_bound(ALL(cy), t[i]) - cy.begin();
		if (u == (int) cx.size() || v == (int) cy.size()) continue;
		queriesAt[u][v].push_back(i);
	}

	CHT cht;
	vector <long long> res(q);
	REP(x, cx.size()) {
		cht.clear();
		REPD(y, cy.size()) {
			cht.addLine(x ? max_hor[x - 1][y] : 0, dp[x][y]);
			for (int i: queriesAt[x][y]) {
				maximize(res[i], cht.getMax(cx[x] - s[i]));
			}

		}
	}
	REP(y, cy.size()) {
		cht.clear();
		REPD(x, cx.size()) {
			cht.addLine(y ? max_ver[x][y - 1] : 0, dp[x][y]);
			for (int i: queriesAt[x][y]) maximize(res[i], cht.getMax(cy[y] - t[i]));
		}
	}
	REP(i, q) cout << res[i] << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("JOI21_bodyguard");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:156:2: note: in expansion of macro 'file'
  156 |  file("JOI21_bodyguard");
      |  ^~~~
bodyguard.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:156:2: note: in expansion of macro 'file'
  156 |  file("JOI21_bodyguard");
      |  ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3404 ms 511736 KB Output is correct
2 Correct 3494 ms 514868 KB Output is correct
3 Correct 1338 ms 218780 KB Output is correct
4 Correct 896 ms 104072 KB Output is correct
5 Correct 1802 ms 817560 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 691880 KB Output is correct
2 Correct 1204 ms 692056 KB Output is correct
3 Correct 1208 ms 682600 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 1158 ms 692052 KB Output is correct
6 Correct 1124 ms 692056 KB Output is correct
7 Correct 1133 ms 690844 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 691880 KB Output is correct
2 Correct 1204 ms 692056 KB Output is correct
3 Correct 1208 ms 682600 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 1158 ms 692052 KB Output is correct
6 Correct 1124 ms 692056 KB Output is correct
7 Correct 1133 ms 690844 KB Output is correct
8 Correct 1203 ms 691980 KB Output is correct
9 Correct 1190 ms 691872 KB Output is correct
10 Correct 1159 ms 681556 KB Output is correct
11 Correct 4 ms 1112 KB Output is correct
12 Correct 1161 ms 691888 KB Output is correct
13 Correct 1132 ms 691908 KB Output is correct
14 Correct 1173 ms 691948 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 691880 KB Output is correct
2 Correct 1204 ms 692056 KB Output is correct
3 Correct 1208 ms 682600 KB Output is correct
4 Correct 2 ms 1116 KB Output is correct
5 Correct 1158 ms 692052 KB Output is correct
6 Correct 1124 ms 692056 KB Output is correct
7 Correct 1133 ms 690844 KB Output is correct
8 Correct 1203 ms 691980 KB Output is correct
9 Correct 1190 ms 691872 KB Output is correct
10 Correct 1159 ms 681556 KB Output is correct
11 Correct 4 ms 1112 KB Output is correct
12 Correct 1161 ms 691888 KB Output is correct
13 Correct 1132 ms 691908 KB Output is correct
14 Correct 1173 ms 691948 KB Output is correct
15 Correct 1254 ms 694864 KB Output is correct
16 Correct 1255 ms 694668 KB Output is correct
17 Correct 1164 ms 684788 KB Output is correct
18 Correct 13 ms 2396 KB Output is correct
19 Correct 1173 ms 693356 KB Output is correct
20 Correct 1158 ms 693608 KB Output is correct
21 Correct 1174 ms 693840 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3404 ms 511736 KB Output is correct
2 Correct 3494 ms 514868 KB Output is correct
3 Correct 1338 ms 218780 KB Output is correct
4 Correct 896 ms 104072 KB Output is correct
5 Correct 1802 ms 817560 KB Output is correct
6 Correct 1183 ms 691880 KB Output is correct
7 Correct 1204 ms 692056 KB Output is correct
8 Correct 1208 ms 682600 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1158 ms 692052 KB Output is correct
11 Correct 1124 ms 692056 KB Output is correct
12 Correct 1133 ms 690844 KB Output is correct
13 Correct 1203 ms 691980 KB Output is correct
14 Correct 1190 ms 691872 KB Output is correct
15 Correct 1159 ms 681556 KB Output is correct
16 Correct 4 ms 1112 KB Output is correct
17 Correct 1161 ms 691888 KB Output is correct
18 Correct 1132 ms 691908 KB Output is correct
19 Correct 1173 ms 691948 KB Output is correct
20 Correct 1254 ms 694864 KB Output is correct
21 Correct 1255 ms 694668 KB Output is correct
22 Correct 1164 ms 684788 KB Output is correct
23 Correct 13 ms 2396 KB Output is correct
24 Correct 1173 ms 693356 KB Output is correct
25 Correct 1158 ms 693608 KB Output is correct
26 Correct 1174 ms 693840 KB Output is correct
27 Correct 4476 ms 915512 KB Output is correct
28 Correct 4520 ms 914924 KB Output is correct
29 Correct 2592 ms 847844 KB Output is correct
30 Correct 781 ms 121196 KB Output is correct
31 Correct 2119 ms 786720 KB Output is correct
32 Correct 3013 ms 850080 KB Output is correct
33 Correct 1896 ms 817920 KB Output is correct