oj.uz

Submission #842471

# Submission time Handle Problem Language Result Execution time Memory
842471 2023-09-02T23:53:54 Z Benq Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 109520 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string;      // yay python!

// pairs
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
#define mp make_pair
#define f first
#define s second

#define tcT template <class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT > using V = vector<T>;
tcT, size_t SZ > using AR = array<T, SZ>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT > int upb(V<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

const int MOD = (int)1e9 + 7;  // 998244353;
const int MX = (int)2e5 + 5;
const ll BIG = 1e18;  // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};  // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set
constexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until
	                         // USACO updates ...
	return x == 0 ? 0 : 31 - __builtin_clz(x);
}  // floor(log2(x))
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }

ll cdiv(ll a, ll b) {
	return a / b + ((a ^ b) > 0 && a % b);
}  // divide a by b rounded up
ll fdiv(ll a, ll b) {
	return a / b - ((a ^ b) < 0 && a % b);
}  // divide a by b rounded down

tcT > bool ckmin(T &a, const T &b) {
	return b < a ? a = b, 1 : 0;
}  // set a = min(a,b)
tcT > bool ckmax(T &a, const T &b) {
	return a < b ? a = b, 1 : 0;
}  // set a = max(a,b)

tcTU > T fstTrue(T lo, T hi, U f) {
	++hi;
	assert(lo <= hi);  // assuming f is increasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo) / 2;
		f(mid) ? hi = mid : lo = mid + 1;
	}
	return lo;
}
tcTU > T lstTrue(T lo, T hi, U f) {
	--lo;
	assert(lo <= hi);  // assuming f is decreasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo + 1) / 2;
		f(mid) ? lo = mid : hi = mid - 1;
	}
	return lo;
}
tcT > void remDup(vector<T> &v) {  // sort and remove duplicates
	sort(all(v));
	v.erase(unique(all(v)), end(v));
}
tcTU > void safeErase(T &t, const U &u) {
	auto it = t.find(u);
	assert(it != end(t));
	t.erase(it);
}

inline namespace IO {
#define SFINAE(x, ...)                                                         \
	template <class, class = void> struct x : std::false_type {};              \
	template <class T> struct x<T, std::void_t<__VA_ARGS__>> : std::true_type {}

SFINAE(DefaultI, decltype(std::cin >> std::declval<T &>()));
SFINAE(DefaultO, decltype(std::cout << std::declval<T &>()));
SFINAE(IsTuple, typename std::tuple_size<T>::type);
SFINAE(Iterable, decltype(std::begin(std::declval<T>())));

template <class T> constexpr char Space(const T &) {
	return (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' ';
}

template <auto &is> struct Reader {
	template <class T> void Impl(T &t) {
		if constexpr (DefaultI<T>::value) is >> t;
		else if constexpr (Iterable<T>::value) {
			for (auto &x : t) Impl(x);
		} else if constexpr (IsTuple<T>::value) {
			std::apply([this](auto &...args) { (Impl(args), ...); }, t);
		} else static_assert(IsTuple<T>::value, "No matching type for read");
	}
	template <class... Ts> void read(Ts &...ts) { ((Impl(ts)), ...); }
};

template <class... Ts> void re(Ts &...ts) { Reader<cin>{}.read(ts...); }
#define def(t, args...)                                                        \
	t args;                                                                    \
	re(args);

template <auto &os, bool debug> struct Writer {
	string comma() const { return debug ? "," : ""; }
	template <class T> void Impl(T const &t) const {
		if constexpr (DefaultO<T>::value) os << t;
		else if constexpr (Iterable<T>::value) {
			if (debug) os << '{';
			int i = 0;
			for (auto &&x : t)
				((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x));
			if (debug) os << '}';
		} else if constexpr (IsTuple<T>::value) {
			if (debug) os << '(';
			std::apply(
			    [this](auto const &...args) {
				    int i = 0;
				    (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)),
				     ...);
			    },
			    t);
			if (debug) os << ')';
		} else static_assert(IsTuple<T>::value, "No matching type for print");
	}
	template <class T> void ImplWrapper(T const &t) const {
		if (debug) os << "\033[0;31m";
		Impl(t);
		if (debug) os << "\033[0m";
	}
	template <class... Ts> void print(Ts const &...ts) const {
		((Impl(ts)), ...);
	}
	template <class F, class... Ts>
	void print_with_sep(const std::string &sep, F const &f,
	                    Ts const &...ts) const {
		ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n';
	}
	void print_with_sep(const std::string &) const { os << '\n'; }
};

template <class... Ts> void pr(Ts const &...ts) {
	Writer<cout, false>{}.print(ts...);
}
template <class... Ts> void ps(Ts const &...ts) {
	Writer<cout, false>{}.print_with_sep(" ", ts...);
}
}  // namespace IO

inline namespace Debug {
template <typename... Args> void err(Args... args) {
	Writer<cerr, true>{}.print_with_sep(" | ", args...);
}

void err_prefix(str func, int line, string args) {
	cerr << "\033[0;31m\u001b[1mDEBUG\033[0m"
	     << " | "
	     << "\u001b[34m" << func << "\033[0m"
	     << ":"
	     << "\u001b[34m" << line << "\033[0m"
	     << " - "
	     << "[" << args << "] = ";
}

#ifdef LOCAL
#define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args)
#else
#define dbg(...)
#endif

const auto beg_time = std::chrono::high_resolution_clock::now();
// https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1
double time_elapsed() {
	return chrono::duration<double>(std::chrono::high_resolution_clock::now() -
	                                beg_time)
	    .count();
}
}  // namespace Debug

inline namespace FileIO {
void setIn(str s) { freopen(s.c_str(), "r", stdin); }
void setOut(str s) { freopen(s.c_str(), "w", stdout); }
void setIO(str s = "") {
	cin.tie(0)->sync_with_stdio(0);  // unsync C / C++ I/O streams
	cout << fixed << setprecision(12);
	// cin.exceptions(cin.failbit);
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) setIn(s + ".in"), setOut(s + ".out");  // for old USACO
}
}  // namespace FileIO

#include "soccer.h"

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	V<vi> row(N, vi(N, -1)), col(N, vi(N, -1));
	F0R(r, N) {
		F0R(c, N) {
			if (F[r][c]) {
				row[r][c] = c;
				col[r][c] = r;
			} else {
				if (c) row[r][c] = row[r][c - 1];
				if (r) col[r][c] = col[r - 1][c];
			}
		}
	}
	auto empty = [&](int r, int c1, int c2) { return row.at(r).at(c2) < c1; };
	V<pair<pi, pi>> rects;
	auto cand_rect = [&](pi x, pi y) {
		if (x.s == N - 1 || row.at(x.s + 1).at(y.s) >= y.f) {
			rects.pb({x, y});
		}
	};
	F0R(r, N) {
		vpi stk{{r, -1}};
		F0R(c, N) {
			// dbg(r, c, col[r][c]);
			while (sz(stk) && stk.bk.f <= col[r][c]) {
				auto p = stk.bk;
				stk.pop_back();
				if (sz(stk) && p.f < col[r][c]) {
					// dbg("HA", p, col[r][c]);
					cand_rect({p.f + 1, r}, {stk.bk.s + 1, c - 1});
				}
			}
			stk.pb({col[r][c], c});
		}
		while (sz(stk)) {
			auto p = stk.bk;
			stk.pop_back();
			if (sz(stk)) {
				// dbg("HA", p, col[r][c]);
				cand_rect({p.f + 1, r}, {stk.bk.s + 1, N - 1});
			}
		}
	}
	auto height = [&](const auto &a) { return a.f.s - a.f.f + 1; };
	auto width = [&](const auto &a) { return a.s.s - a.s.f + 1; };
	sort(all(rects), [](const auto &a, const auto &b) {
		return a.s.s - a.s.f + 1 < b.s.s - b.s.f + 1;
	});

	V<pair<pair<pi, pi>, int>> order;
	F0R(i, sz(rects)) { order.pb({rects[i], i}); }

	auto locate = [&](pair<pi, pi> p) {
		// dbg("LOCATE", p);
		int i = lwb(order, {p, 0});
		assert(order.at(i).f == p);
		// dbg("DONE LOCATE");
		return order.at(i).s;
	};
	sor(order);
	auto contains = [&](pi a, pi b) {
		return a.f <= b.f && b.s <= a.s && a != b;
	};
	vi dp(sz(rects));
	int ans = 0;
	F0R(i, sz(rects)) {
		int r1 = rects[i].f.f;
		int r2 = rects[i].f.s;
		int c1 = rects[i].s.f;
		int c2 = rects[i].s.s;

		auto cand_rect = [&](int c_lo, int c_hi) {
			assert(c_lo <= c_hi);
			int r_lo = r1;
			int r_hi = r2;
			while (r_lo && empty(r_lo - 1, c_lo, c_hi)) --r_lo;
			while (r_hi + 1 < N && empty(r_hi + 1, c_lo, c_hi)) ++r_hi;
			int j = locate({{r_lo, r_hi}, {c_lo, c_hi}});
			ckmax(dp[i], dp[j] + (height(rects[j]) - height(rects[i])) *
			                         width(rects[j]));
		};

		// dbg("BEGIN");
		for (int r : {r1 - 1, r2 + 1}) {
			int c = c2 + 1;
			while (c > c1) {
				// dbg(r, c);
				int prev_c =
				    ((r < 0 || r >= N) ? c - 1
				                       : max(row.at(r).at(c - 1), c1 - 1));
				if (prev_c + 1 < c) { cand_rect(prev_c + 1, c - 1); }
				c = prev_c;
			}
			// dbg("HI");
		}
		// dbg("END");
		ckmax(ans, dp[i] + height(rects[i]) * width(rects[i]));
	}
	return ans;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int, std::allocator<int> > >)':
soccer.cpp:316:7: warning: variable 'contains' set but not used [-Wunused-but-set-variable]
  316 |  auto contains = [&](pi a, pi b) {
      |       ^~~~~~~~
soccer.cpp: In function 'void FileIO::setIn(str)':
soccer.cpp:242:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 | void setIn(str s) { freopen(s.c_str(), "r", stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp: In function 'void FileIO::setOut(str)':
soccer.cpp:243:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 | void setOut(str s) { freopen(s.c_str(), "w", stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 18 ms 4188 KB ok
9 Correct 288 ms 63312 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 1 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 1 ms 344 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 0 ms 344 KB ok
31 Correct 1 ms 344 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 344 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 60 ms 7064 KB ok
43 Correct 59 ms 7236 KB ok
44 Correct 31 ms 5044 KB ok
45 Correct 26 ms 4792 KB ok
46 Correct 48 ms 6676 KB ok
47 Correct 18 ms 4440 KB ok
48 Correct 20 ms 4248 KB ok
49 Correct 18 ms 4444 KB ok
50 Correct 94 ms 4432 KB ok
51 Correct 23 ms 5588 KB ok
52 Correct 18 ms 4440 KB ok
53 Correct 18 ms 4444 KB ok
54 Correct 18 ms 4440 KB ok
55 Correct 19 ms 4444 KB ok
56 Correct 22 ms 4188 KB ok
57 Correct 44 ms 7232 KB ok
58 Correct 51 ms 9228 KB ok
59 Correct 55 ms 10432 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 604 KB ok
9 Correct 18 ms 4188 KB ok
10 Correct 288 ms 63312 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 344 KB ok
36 Correct 1 ms 344 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 0 ms 344 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 0 ms 348 KB ok
44 Correct 0 ms 348 KB ok
45 Correct 0 ms 348 KB ok
46 Correct 0 ms 348 KB ok
47 Correct 60 ms 7064 KB ok
48 Correct 59 ms 7236 KB ok
49 Correct 31 ms 5044 KB ok
50 Correct 26 ms 4792 KB ok
51 Correct 48 ms 6676 KB ok
52 Correct 18 ms 4440 KB ok
53 Correct 20 ms 4248 KB ok
54 Correct 18 ms 4444 KB ok
55 Correct 94 ms 4432 KB ok
56 Correct 23 ms 5588 KB ok
57 Correct 18 ms 4440 KB ok
58 Correct 18 ms 4444 KB ok
59 Correct 18 ms 4440 KB ok
60 Correct 19 ms 4444 KB ok
61 Correct 22 ms 4188 KB ok
62 Correct 44 ms 7232 KB ok
63 Correct 51 ms 9228 KB ok
64 Correct 55 ms 10432 KB ok
65 Correct 1364 ms 109520 KB ok
66 Correct 526 ms 107940 KB ok
67 Correct 358 ms 85492 KB ok
68 Correct 557 ms 65736 KB ok
69 Correct 892 ms 74672 KB ok
70 Correct 1140 ms 87676 KB ok
71 Correct 420 ms 64660 KB ok
72 Correct 282 ms 63316 KB ok
73 Correct 282 ms 63516 KB ok
74 Correct 279 ms 63316 KB ok
75 Correct 281 ms 63372 KB ok
76 Execution timed out 4525 ms 63312 KB Time limit exceeded
77 Halted 0 ms 0 KB -