oj.uz

Submission #454946

# Submission time Handle Problem Language Result Execution time Memory
454946 2021-08-05T10:47:05 Z nonsensenonsense1 Boat (APIO16_boat) C++17
9 / 100
 261 ms 2308 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2308 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct
3 Correct 4 ms 2252 KB Output is correct
4 Correct 4 ms 2252 KB Output is correct
5 Correct 4 ms 2216 KB Output is correct
6 Correct 3 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 4 ms 2256 KB Output is correct
10 Correct 4 ms 2252 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2252 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 4 ms 2252 KB Output is correct
15 Correct 4 ms 2252 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2308 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct
3 Correct 4 ms 2252 KB Output is correct
4 Correct 4 ms 2252 KB Output is correct
5 Correct 4 ms 2216 KB Output is correct
6 Correct 3 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 4 ms 2256 KB Output is correct
10 Correct 4 ms 2252 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2252 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 4 ms 2252 KB Output is correct
15 Correct 4 ms 2252 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Incorrect 261 ms 2088 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2308 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct
3 Correct 4 ms 2252 KB Output is correct
4 Correct 4 ms 2252 KB Output is correct
5 Correct 4 ms 2216 KB Output is correct
6 Correct 3 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 3 ms 2252 KB Output is correct
9 Correct 4 ms 2256 KB Output is correct
10 Correct 4 ms 2252 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2252 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 4 ms 2252 KB Output is correct
15 Correct 4 ms 2252 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Incorrect 261 ms 2088 KB Output isn't correct
22 Halted 0 ms 0 KB -