oj.uz

답안 #107036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107036 2019-04-21T13:43:49 Z qoo2p5 Boat (APIO16_boat) C++17
9 / 100
 1124 ms 6524 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, t) for (int i = s; i < t; i++)
#define per(i, s, t) for (int i = s; i >= t; i--)
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = (int) (1e9 + 1e6 + 123);

template<typename A, typename B> bool mini(A& x, const B& y) {
	if (y < x) {
		x = y;
		return true;
	}
	return false;
}

template<typename A, typename B> bool maxi(A& x, const B& y) {
	if (y > x) {
		x = y;
		return true;
	}
	return false;
}

void run();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	run();
	return 0;
}

const int N = 505;
const int MOD = 1000000000 + 7;

void add(int& x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
}

int power(int x, int y) {
	if (y == 0) {
		return 1;
	}
	if (y % 2 == 0) {
		return power(x * 1LL * x % MOD, y / 2);
	} else {
		return power(x, y - 1) * 1LL * x % MOD;
	}
}

int n;
int a[N], b[N];
vector<int> cool;

int fact[N];
int rfact[N];
int dp[2 * N][N];
int nxt[2 * N][N];
int prec[2 * N][N];

int cnk(int n, int k) {
	if (k > n) {
		return 0;
	}
	int res = 1;
	rep(i, 0, k) {
		res = res * 1LL * (n - i) % MOD;
	}
	res = res * 1LL * rfact[k] % MOD;
	return res;
}

void upd(int l, int r) {
	memcpy(nxt, dp, sizeof dp);

	int pref = 0;
	rep(block, 0, sz(cool)) {
		if (l <= block && block <= r) {
			int len = cool[block + 1] - cool[block];
			add(nxt[block][1], pref * 1LL * len % MOD);
		}
		rep(cnt, 0, N) {
			add(pref, dp[block][cnt]);
		}
	}

	rep(block, 0, sz(cool)) {
		if (l <= block && block <= r) {
			rep(cnt, 2, N) {
				add(nxt[block][cnt], dp[block][cnt - 1] * 1LL * prec[block][cnt - 1] % MOD);
			}
		}
	}

	swap(nxt, dp);
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> a[i] >> b[i];
		cool.push_back(a[i]);
		cool.push_back(b[i] + 1);
	}
	cool.push_back(0);
	sort(all(cool));
	cool.resize(unique(all(cool)) - cool.begin());
	cool.push_back(INF);

	fact[0] = 1;
	rep(i, 1, N) {
		fact[i] = fact[i - 1] * 1LL * i % MOD;
	}
	rep(i, 0, N) {
		rfact[i] = power(fact[i], MOD - 2);
	}

	rep(i, 0, sz(cool) - 1) {
		rep(x, 1, N) {
			int len = cool[i + 1] - cool[i];
			prec[i][x] = cnk(len, x + 1);
		}
	}

	dp[0][0] = 1;
	rep(i, 0, n) {
		int l = 0;
		while (cool[l] != a[i]) {
			l++;
		}
		int r = l;
		while (cool[r + 1] <= b[i]) {
			r++;
		}
		upd(l, r);
	}

	int ans = MOD - 1;
	rep(i, 0, 2 * N) {
		rep(j, 0, N) {
			add(ans, dp[i][j]);
		}
	}
	cout << ans << "\n";
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1051 ms 6468 KB Output is correct
2 Correct 1089 ms 6520 KB Output is correct
3 Correct 1080 ms 6512 KB Output is correct
4 Correct 1079 ms 6492 KB Output is correct
5 Correct 1076 ms 6488 KB Output is correct
6 Correct 1097 ms 6392 KB Output is correct
7 Correct 1099 ms 6520 KB Output is correct
8 Correct 1079 ms 6392 KB Output is correct
9 Correct 1124 ms 6524 KB Output is correct
10 Correct 1067 ms 6508 KB Output is correct
11 Correct 1059 ms 6392 KB Output is correct
12 Correct 1103 ms 6520 KB Output is correct
13 Correct 1123 ms 6484 KB Output is correct
14 Correct 1104 ms 6392 KB Output is correct
15 Correct 1113 ms 6392 KB Output is correct
16 Correct 455 ms 4744 KB Output is correct
17 Correct 523 ms 4856 KB Output is correct
18 Correct 486 ms 4856 KB Output is correct
19 Correct 480 ms 4728 KB Output is correct
20 Correct 535 ms 4760 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1051 ms 6468 KB Output is correct
2 Correct 1089 ms 6520 KB Output is correct
3 Correct 1080 ms 6512 KB Output is correct
4 Correct 1079 ms 6492 KB Output is correct
5 Correct 1076 ms 6488 KB Output is correct
6 Correct 1097 ms 6392 KB Output is correct
7 Correct 1099 ms 6520 KB Output is correct
8 Correct 1079 ms 6392 KB Output is correct
9 Correct 1124 ms 6524 KB Output is correct
10 Correct 1067 ms 6508 KB Output is correct
11 Correct 1059 ms 6392 KB Output is correct
12 Correct 1103 ms 6520 KB Output is correct
13 Correct 1123 ms 6484 KB Output is correct
14 Correct 1104 ms 6392 KB Output is correct
15 Correct 1113 ms 6392 KB Output is correct
16 Correct 455 ms 4744 KB Output is correct
17 Correct 523 ms 4856 KB Output is correct
18 Correct 486 ms 4856 KB Output is correct
19 Correct 480 ms 4728 KB Output is correct
20 Correct 535 ms 4760 KB Output is correct
21 Incorrect 920 ms 6224 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 260 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1051 ms 6468 KB Output is correct
2 Correct 1089 ms 6520 KB Output is correct
3 Correct 1080 ms 6512 KB Output is correct
4 Correct 1079 ms 6492 KB Output is correct
5 Correct 1076 ms 6488 KB Output is correct
6 Correct 1097 ms 6392 KB Output is correct
7 Correct 1099 ms 6520 KB Output is correct
8 Correct 1079 ms 6392 KB Output is correct
9 Correct 1124 ms 6524 KB Output is correct
10 Correct 1067 ms 6508 KB Output is correct
11 Correct 1059 ms 6392 KB Output is correct
12 Correct 1103 ms 6520 KB Output is correct
13 Correct 1123 ms 6484 KB Output is correct
14 Correct 1104 ms 6392 KB Output is correct
15 Correct 1113 ms 6392 KB Output is correct
16 Correct 455 ms 4744 KB Output is correct
17 Correct 523 ms 4856 KB Output is correct
18 Correct 486 ms 4856 KB Output is correct
19 Correct 480 ms 4728 KB Output is correct
20 Correct 535 ms 4760 KB Output is correct
21 Incorrect 920 ms 6224 KB Output isn't correct
22 Halted 0 ms 0 KB -