Submission #454946

#	Time	Username	Problem	Language	Result	Execution time	Memory
454946		nonsensenonsense1	Boat (APIO16_boat)	C++17	9 / 100	261 ms	2308 KiB

boat

#include <cstdio>
#include <algorithm>

const int md = 1000000007;

inline int add(int a, int b) 
{
	a += b;
	if (a >= md) a -= md;
	return a;
}
inline int sub(int a, int b) 
{
	a -= b;
	if (a < 0) a += md;
	return a;
}
inline int mul(int a, int b) 
{
	return (long long)a * b % md;
}
int po(int a, int b) 
{
	int r = 1;
	while (b) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}
inline int inv(int a) 
{
	return po(a, md - 2);
}
inline int di(int a, int b) 
{
	return mul(a, inv(b));
}

const int N = 505;
int n, d[N << 1], l[N], r[N], a[N << 1], p[N << 1][N], amt[N], single[N << 1];

int main() 
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", l + i, r + i);
		a[i << 1] = l[i];
		a[i << 1 | 1] = r[i] + 1;
	}
	std::sort(a, a + n * 2);
	int len = std::unique(a, a + n * 2) - a;
	d[0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = len - 1; j >= 1; --j) if (l[i] <= a[j - 1] && r[i] >= a[j] - 1) {
			d[j] = add(d[j], sub(d[j], single[j]));
			for (int k = j - 1; k >= 0; --k) p[j][amt[j]] = add(p[j][amt[j]], d[k]);
			for (int k = std::max(0, amt[j] + 1 - a[j] + a[j - 1]); k <= amt[j]; ++k) {
				p[j][k] = mul(p[j][k], a[j] - a[j - 1] - amt[j] + k);
				p[j][k] = di(p[j][k], amt[j] - k + 1);
				d[j] = add(d[j], p[j][k]);
			}
			single[j] = add(single[j], p[j][amt[j]]);
			++amt[j];
		}
	}
	int ans = 0;
	for (int i = 1; i < len; ++i) ans = add(ans, d[i]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", l + i, r + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42