oj.uz

Submission #892679

# Submission time Handle Problem Language Result Execution time Memory
892679 2023-12-25T16:47:07 Z marvinthang Bodyguard (JOI21_bodyguard) C++17
100 / 100
 6938 ms 944520 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 ((int) lines.size() == 1) return lines[0].eval(x);
    	long long res = 0;
    	for (Line l: lines) res = max(res, l.eval(x));
        // 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;
        // }
        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 3427 ms 511580 KB Output is correct
2 Correct 3335 ms 514756 KB Output is correct
3 Correct 1250 ms 218684 KB Output is correct
4 Correct 844 ms 104272 KB Output is correct
5 Correct 1725 ms 818220 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 691972 KB Output is correct
2 Correct 1128 ms 691820 KB Output is correct
3 Correct 1107 ms 682396 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1095 ms 691860 KB Output is correct
6 Correct 1073 ms 691864 KB Output is correct
7 Correct 1111 ms 690772 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 691972 KB Output is correct
2 Correct 1128 ms 691820 KB Output is correct
3 Correct 1107 ms 682396 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1095 ms 691860 KB Output is correct
6 Correct 1073 ms 691864 KB Output is correct
7 Correct 1111 ms 690772 KB Output is correct
8 Correct 1382 ms 692068 KB Output is correct
9 Correct 1214 ms 691812 KB Output is correct
10 Correct 1096 ms 681020 KB Output is correct
11 Correct 5 ms 1116 KB Output is correct
12 Correct 1125 ms 691924 KB Output is correct
13 Correct 1088 ms 691960 KB Output is correct
14 Correct 1119 ms 691864 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 691972 KB Output is correct
2 Correct 1128 ms 691820 KB Output is correct
3 Correct 1107 ms 682396 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1095 ms 691860 KB Output is correct
6 Correct 1073 ms 691864 KB Output is correct
7 Correct 1111 ms 690772 KB Output is correct
8 Correct 1382 ms 692068 KB Output is correct
9 Correct 1214 ms 691812 KB Output is correct
10 Correct 1096 ms 681020 KB Output is correct
11 Correct 5 ms 1116 KB Output is correct
12 Correct 1125 ms 691924 KB Output is correct
13 Correct 1088 ms 691960 KB Output is correct
14 Correct 1119 ms 691864 KB Output is correct
15 Correct 1194 ms 694608 KB Output is correct
16 Correct 1188 ms 694872 KB Output is correct
17 Correct 1118 ms 685032 KB Output is correct
18 Correct 21 ms 2352 KB Output is correct
19 Correct 1160 ms 693272 KB Output is correct
20 Correct 1160 ms 693588 KB Output is correct
21 Correct 1121 ms 693856 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3427 ms 511580 KB Output is correct
2 Correct 3335 ms 514756 KB Output is correct
3 Correct 1250 ms 218684 KB Output is correct
4 Correct 844 ms 104272 KB Output is correct
5 Correct 1725 ms 818220 KB Output is correct
6 Correct 1108 ms 691972 KB Output is correct
7 Correct 1128 ms 691820 KB Output is correct
8 Correct 1107 ms 682396 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1095 ms 691860 KB Output is correct
11 Correct 1073 ms 691864 KB Output is correct
12 Correct 1111 ms 690772 KB Output is correct
13 Correct 1382 ms 692068 KB Output is correct
14 Correct 1214 ms 691812 KB Output is correct
15 Correct 1096 ms 681020 KB Output is correct
16 Correct 5 ms 1116 KB Output is correct
17 Correct 1125 ms 691924 KB Output is correct
18 Correct 1088 ms 691960 KB Output is correct
19 Correct 1119 ms 691864 KB Output is correct
20 Correct 1194 ms 694608 KB Output is correct
21 Correct 1188 ms 694872 KB Output is correct
22 Correct 1118 ms 685032 KB Output is correct
23 Correct 21 ms 2352 KB Output is correct
24 Correct 1160 ms 693272 KB Output is correct
25 Correct 1160 ms 693588 KB Output is correct
26 Correct 1121 ms 693856 KB Output is correct
27 Correct 4396 ms 944520 KB Output is correct
28 Correct 4307 ms 943904 KB Output is correct
29 Correct 2494 ms 876900 KB Output is correct
30 Correct 1268 ms 150312 KB Output is correct
31 Correct 4670 ms 801380 KB Output is correct
32 Correct 6938 ms 870160 KB Output is correct
33 Correct 1955 ms 854348 KB Output is correct