oj.uz

Submission #918958

# Submission time Handle Problem Language Result Execution time Memory
918958 2024-01-31T00:13:23 Z mpb_ Team Contest (JOI22_team) C++17
100 / 100
 325 ms 36176 KB 
/* हर हर महादेव */

#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;
using ull = uint64_t;
using ld = long double;

#define int int64_t

using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define mp make_pair
#define fi first
#define se second

template <class T> using vt = vector<T>;
template <class T> using vvt = vt<vt<T>>;
template <class T> using vvvt = vt<vvt<T>>;

#define all(v) (v).begin(), (v).end()
#define si(x) (int)(x).size()
#define pb push_back
#define eb emplace_back

int d4x[4] = {-1, 0, 1, 0};
int d4y[4] = {0, -1, 0, 1};

const ld PI = 3.1415926535897932384626433832795;

template <typename T> using max_heap = priority_queue<T, vt<T>, std::less<T>>;
template <typename T> using min_heap = priority_queue<T, vt<T>, std::greater<T>>;

#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d

#define FOR2(i, a) for (int i = 0; i <= (int)(a); i++)
#define FOR3(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define FOR4(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2)(__VA_ARGS__)

#define ROF2(i, a) for (int i = (int)(a); i >= 0; i--)
#define ROF3(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define ROF4(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define ROF(...) overload4(__VA_ARGS__, ROF4, ROF3, ROF2)(__VA_ARGS__)

template <class, class = void> struct Readable : std::false_type {};
template <class T> struct Readable<T, std::void_t<decltype(std::cin >> std::declval<T&>())>> : std::true_type {};

template <class, class = void> struct Printable : std::false_type {};
template <class T> struct Printable<T, std::void_t<decltype(std::cout << std::declval<T&>())>> : std::true_type {};

template <class, class = void> struct Iterable : std::false_type {};
template <class T> struct Iterable<T, std::void_t<decltype(std::begin(std::declval<T>()))>> : std::true_type {};

template <class, class = void> struct Tuplelike : std::false_type {};
template <class T> struct Tuplelike<T, std::void_t<typename std::tuple_size<T>::type>> : std::true_type {};

struct Scanner {
	void read() {}
	template <class H, class... T> void read(H& h, T&... t) {
		read_single(h);
		read(t...);
	}
	template <typename T> void read_single(T& t) {
		if constexpr (Readable<T>::value) {
			cin >> t;
		} else if constexpr (Tuplelike<T>::value) {
			apply([&](auto&... args) { (read_single(args), ...); }, t);
		} else if constexpr (Iterable<T>::value) {
			for (auto& x : t) read_single(x);
		} else static_assert(Tuplelike<T>::value, "No matching type for read");
	}
} sc;

template <auto& os, bool debug> struct Printer {
	const string sep = debug ? ", " : " ";
	template <class H, class... T> void write(const H& h, const T&... t) {
		write_single(h);
		(void)(..., (write_single(t)));
	}
	template <class H, class... T> void writeln(const H& h, const T&... t) {
		write_single(h);
		(void)(..., (os << sep, write_single(t)));
		os << '\n';
	}
	template <typename T> void write_single(T& t) {
		if constexpr (Printable<T>::value) {
			os << t;
		} else if constexpr (Tuplelike<T>::value) {
			if (debug) os << '(';
			apply([&](const auto&... args) {
				bool fst = true;
				((fst ? (fst = false, write_single(args)) : (os << sep, write_single(args))), ...);
			}, t);
			if (debug) os << ')';
		} else if constexpr (Iterable<T>::value) {
			if (debug) os << '{';
			for (bool fst = true; const auto& x : t) os << (fst ? fst = false, "" : sep), write_single(x);
			if (debug) os << '}';
		} else static_assert(Tuplelike<T>::value, "No matching type for print");
	}
};

Printer<cout, false> pr;
Printer<cerr, true> tr;

template <class H, typename... T>
void read(H& h, T&... t) {
	sc.read(h, t...);
}

template <class H, typename... T>
void write(const H& h, const T&... t) {
	pr.write(h, t...);
}

template <class H, typename... T> 
void print(const H& h, const T&... t) {
	pr.writeln(h, t...);
}

template <class H, typename... T>
void trace(const H& h, const T&... t) {
	tr.writeln(h, t...);
}

#ifdef LOCAL
#define dbg(...) cerr << __func__ << ':' << __LINE__ << " (" << #__VA_ARGS__ << "): ", trace(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

template <class T, class S> bool chmax(T& a, S b) { if (a < b) { a = b; return true; } else return false; }
template <class T, class S> bool chmin(T& a, S b) { if (b < a) { a = b; return true; } else return false; } 

template <class T,class S = ll>
S SUM(const vt<T> &a) {
	return accumulate(all(a), S(0));
}

template <class T>
T MAX(const vt<T> &a) {
	return *max_element(all(a));
}

template <class T>
T MIN(const vt<T> &a) {
	return *min_element(all(a));
}

template <class T> 
void mkuni(vt<T> &v) {
	sort(all(v));
	v.erase(unique(all(v)), v.end());
}

template <class T>
vt<int> sortidx(const vt<T> &a) {
	int n = si(a);
	vt<int> idx(n); iota(all(idx),0);
	sort(all(idx),[&](int i,int j){ return a[i] < a[j]; });
	return idx;
}

template <class T>
vt<T> prefsum(const vt<T>& a) {
	int n = si(a);
	vt<T> psum(n + 1);
	for (int i = 1; i <= n; i++) psum[i] = psum[i - 1] + a[i - 1];
	return psum;
}

template <class T>
vt<T> suffsum(const vt<T>& a) {
	int n = si(a);
	vt<T> ssum(n + 1);
	for (int i = n - 1; i >= 0; i--) ssum[i] = ssum[i + 1] + a[i];
	return ssum;
}

template <class T>
T fdiv(T x, T y) {
	assert(y != 0);
	if (y < 0) { x = -x; y = -y; }
	if (x >= 0) return x/y;
	return (x+1)/y - 1;
}

template <class T>
T cdiv(T x, T y) {
	assert(y != 0);
	if (y < 0) { x = -x; y = -y; }
	if (x <= 0) return x/y;
	return (x-1)/y + 1;
}

template <typename T>
T isqrt(T a) {
	T x = T(sqrt(a)) + 2;
	while (1LL * x * x > a) x--;
	return x;
}

void sol() {
	int N; read(N);
	vt<array<int, 3>> B(N); read(B);
	set<pii> x, y, z;
	FOR(i, N - 1) {
		x.emplace(B[i][0], i);
		y.emplace(B[i][1], i);
		z.emplace(B[i][2], i);
	}
	int ans = -1;
	while (min(si(x), min(si(y), si(z))) > 0) {
		auto [xval, id1] = *x.rbegin();
		auto [yval, id2] = *y.rbegin();
		auto [zval, id3] = *z.rbegin();
		bool okx = (B[id1][1] < yval && B[id1][2] < zval);
		bool oky = (B[id2][0] < xval && B[id2][2] < zval);
		bool okz = (B[id3][0] < xval && B[id3][1] < yval);
		if (okx && oky && okz) {
			ans = max(ans, xval + yval + zval);
			break;
		}
		if (!okx) {
			x.erase({xval, id1});
		}
		if (!oky) {
			y.erase({yval, id2});
		} 
		if (!okz) {
			z.erase({zval, id3});
		}
	}
	print(ans);
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);
	int tc = 1; 
	// read(tc);
	while (tc--) sol();
}

Compilation message

team.cpp: In member function 'void Printer<os, debug>::write_single(T&)':
team.cpp:101:26: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  101 |    for (bool fst = true; const auto& x : t) os << (fst ? fst = false, "" : sep), write_single(x);
      |                          ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 3 ms 1368 KB Output is correct
27 Correct 4 ms 1368 KB Output is correct
28 Correct 4 ms 1368 KB Output is correct
29 Correct 4 ms 1368 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 3 ms 1112 KB Output is correct
32 Correct 4 ms 1112 KB Output is correct
33 Correct 3 ms 1368 KB Output is correct
34 Correct 3 ms 1368 KB Output is correct
35 Correct 2 ms 756 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 2 ms 1112 KB Output is correct
38 Correct 3 ms 1112 KB Output is correct
39 Correct 2 ms 856 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 176 ms 33016 KB Output is correct
12 Correct 98 ms 22096 KB Output is correct
13 Correct 108 ms 27216 KB Output is correct
14 Correct 167 ms 32908 KB Output is correct
15 Correct 132 ms 32848 KB Output is correct
16 Correct 133 ms 32848 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 176 ms 33016 KB Output is correct
12 Correct 98 ms 22096 KB Output is correct
13 Correct 108 ms 27216 KB Output is correct
14 Correct 167 ms 32908 KB Output is correct
15 Correct 132 ms 32848 KB Output is correct
16 Correct 133 ms 32848 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 186 ms 33204 KB Output is correct
23 Correct 166 ms 32180 KB Output is correct
24 Correct 127 ms 24144 KB Output is correct
25 Correct 170 ms 33108 KB Output is correct
26 Correct 142 ms 32996 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 176 ms 33016 KB Output is correct
12 Correct 98 ms 22096 KB Output is correct
13 Correct 108 ms 27216 KB Output is correct
14 Correct 167 ms 32908 KB Output is correct
15 Correct 132 ms 32848 KB Output is correct
16 Correct 133 ms 32848 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 186 ms 33204 KB Output is correct
23 Correct 166 ms 32180 KB Output is correct
24 Correct 127 ms 24144 KB Output is correct
25 Correct 170 ms 33108 KB Output is correct
26 Correct 142 ms 32996 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 4 ms 1112 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 251 ms 32040 KB Output is correct
35 Correct 225 ms 30464 KB Output is correct
36 Correct 255 ms 33660 KB Output is correct
37 Correct 239 ms 33360 KB Output is correct
38 Correct 147 ms 32848 KB Output is correct
39 Correct 85 ms 20440 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 176 ms 33016 KB Output is correct
12 Correct 98 ms 22096 KB Output is correct
13 Correct 108 ms 27216 KB Output is correct
14 Correct 167 ms 32908 KB Output is correct
15 Correct 132 ms 32848 KB Output is correct
16 Correct 133 ms 32848 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 186 ms 33204 KB Output is correct
23 Correct 166 ms 32180 KB Output is correct
24 Correct 127 ms 24144 KB Output is correct
25 Correct 170 ms 33108 KB Output is correct
26 Correct 142 ms 32996 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 4 ms 1112 KB Output is correct
32 Correct 1 ms 600 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 251 ms 32040 KB Output is correct
35 Correct 225 ms 30464 KB Output is correct
36 Correct 255 ms 33660 KB Output is correct
37 Correct 239 ms 33360 KB Output is correct
38 Correct 147 ms 32848 KB Output is correct
39 Correct 85 ms 20440 KB Output is correct
40 Correct 3 ms 856 KB Output is correct
41 Correct 3 ms 1112 KB Output is correct
42 Correct 4 ms 1112 KB Output is correct
43 Correct 3 ms 1112 KB Output is correct
44 Correct 318 ms 34208 KB Output is correct
45 Correct 319 ms 34144 KB Output is correct
46 Correct 286 ms 34128 KB Output is correct
47 Correct 266 ms 34128 KB Output is correct
48 Correct 162 ms 34128 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 3 ms 1368 KB Output is correct
27 Correct 4 ms 1368 KB Output is correct
28 Correct 4 ms 1368 KB Output is correct
29 Correct 4 ms 1368 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 3 ms 1112 KB Output is correct
32 Correct 4 ms 1112 KB Output is correct
33 Correct 3 ms 1368 KB Output is correct
34 Correct 3 ms 1368 KB Output is correct
35 Correct 2 ms 756 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 2 ms 1112 KB Output is correct
38 Correct 3 ms 1112 KB Output is correct
39 Correct 2 ms 856 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 0 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 344 KB Output is correct
50 Correct 176 ms 33016 KB Output is correct
51 Correct 98 ms 22096 KB Output is correct
52 Correct 108 ms 27216 KB Output is correct
53 Correct 167 ms 32908 KB Output is correct
54 Correct 132 ms 32848 KB Output is correct
55 Correct 133 ms 32848 KB Output is correct
56 Correct 0 ms 344 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 344 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 1 ms 856 KB Output is correct
61 Correct 186 ms 33204 KB Output is correct
62 Correct 166 ms 32180 KB Output is correct
63 Correct 127 ms 24144 KB Output is correct
64 Correct 170 ms 33108 KB Output is correct
65 Correct 142 ms 32996 KB Output is correct
66 Correct 1 ms 344 KB Output is correct
67 Correct 1 ms 344 KB Output is correct
68 Correct 1 ms 348 KB Output is correct
69 Correct 1 ms 344 KB Output is correct
70 Correct 4 ms 1112 KB Output is correct
71 Correct 1 ms 600 KB Output is correct
72 Correct 1 ms 600 KB Output is correct
73 Correct 251 ms 32040 KB Output is correct
74 Correct 225 ms 30464 KB Output is correct
75 Correct 255 ms 33660 KB Output is correct
76 Correct 239 ms 33360 KB Output is correct
77 Correct 147 ms 32848 KB Output is correct
78 Correct 85 ms 20440 KB Output is correct
79 Correct 3 ms 856 KB Output is correct
80 Correct 3 ms 1112 KB Output is correct
81 Correct 4 ms 1112 KB Output is correct
82 Correct 3 ms 1112 KB Output is correct
83 Correct 318 ms 34208 KB Output is correct
84 Correct 319 ms 34144 KB Output is correct
85 Correct 286 ms 34128 KB Output is correct
86 Correct 266 ms 34128 KB Output is correct
87 Correct 162 ms 34128 KB Output is correct
88 Correct 318 ms 35956 KB Output is correct
89 Correct 317 ms 36176 KB Output is correct
90 Correct 324 ms 35872 KB Output is correct
91 Correct 274 ms 36000 KB Output is correct
92 Correct 324 ms 34648 KB Output is correct
93 Correct 280 ms 34896 KB Output is correct
94 Correct 325 ms 34644 KB Output is correct
95 Correct 195 ms 35920 KB Output is correct
96 Correct 198 ms 35920 KB Output is correct
97 Correct 158 ms 35972 KB Output is correct
98 Correct 159 ms 34640 KB Output is correct
99 Correct 152 ms 34640 KB Output is correct