Submission #1356069

#TimeUsernameProblemLanguageResultExecution timeMemory
1356069jinhan814Boat (APIO16_boat)C++20
Compilation error
0 ms0 KiB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int mod = 1e9 + 7;

constexpr int add(int a, int b) {
	return a + b < mod ? a + b : a + b - mod;
}

constexpr int sub(int a, int b) {
	return a < b ? a - b + mod : a - b;
}

constexpr int mul(int a, int b) {
	return i64(a) * b % mod;
}

constexpr int pow(int x, int n) {
	int ret = 1;
	for (; n; n >>= 1) {
		if (n & 1) ret = mul(ret, x);
		x = mul(x, x);
	}
	return ret;
}

auto sol = [](int n, auto l, auto r) {
	vector c(0, 0);
	for (int i = 0; i < n; i++) {
		c.push_back(l[i]);
		c.push_back(r[i] + 1);
	}
	sort(c.begin(), c.end());
	c.erase(unique(c.begin(), c.end()), c.end());
	vector d(n + 1, 1);
	for (int i = 1; i <= n; i++) d[n] = mul(d[n], i);
	d[n] = pow(d[n], mod - 2);
	for (int i = n; i >= 1; i--) d[i - 1] = mul(d[i], i);
	for (int i = 0; i <= n / 2; i++) d[n - i] = d[i] = mul(d[i], d[n - i]);
	vector f(n + 1, 0);
	vector s(n + 2, 1);
	auto calc = [&](int x) {
		if (x <= n) return f[x];
		for (int i = n; i >= 0; i--) s[i] = mul(s[i + 1], x - i);
		int ret = 0;
		int acc = 1;
		for (int i = 0; i <= n; i++) {
			int val = mul(mul(f[i], d[i]), mul(acc, s[i + 1]));
			acc = mul(acc, sub(x, i));
			if ((n - i) % 2 == 0) ret = add(ret, val);
			else ret = sub(ret, val);
		}
		return ret;
	};
	int m = c.size() - 1;
	vector dp(m * (n + 1), 0);
	for (int iter = 0; iter < n; iter++) {
		int acc = 1;
		for (int i = 0; c[i] <= r[iter]; i++) {
			f[0] = dp[i * (n + 1)];
			for (int j = 1; j <= n; j++) f[j] = add(f[j - 1], dp[i * (n + 1) + j]);
			if (c[i] >= l[iter]) {
				int val = acc;
				for (int j = 0; j <= n; j++) {
					int prv = dp[i * (n + 1) + j];
					dp[i * (n + 1) + j] = add(dp[i * (n + 1) + j], val);
					val = add(val, prv);
				}
			}
			acc = add(acc, calc(c[i + 1] - c[i] - 1));
		}
	}
	int ret = 0;
	for (int i = 0; i < m; i++) {
		f[0] = dp[i * (n + 1)];
		for (int j = 1; j <= n; j++) f[j] = add(f[j - 1], dp[i * (n + 1) + j]);
		ret = add(ret, calc(c[i + 1] - c[i] - 1));
	}
	return ret;
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	vector l(n, 0), r(n, 0);
	for (int i = 0; i < n; i++) cin >> l[i] >> r[i];
	cout << sol(n, l, r) << '\n';
}

Compilation message (stderr)

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from boat.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor 'constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~