Submission #949334

#	Time	Username	Problem	Language	Result	Execution time	Memory
949334		IBory	Boat (APIO16_boat)	C++17	100 / 100	257 ms	2128 KiB

boat

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll MAX = 1007, MOD = 1E9 + 7;
ll L[MAX], R[MAX], F[MAX], IF[MAX], C[MAX], all[MAX], temp[MAX];
vector<int> S[MAX];

ll Pow(ll N, ll K) {
	ll ret = 1;
	while (K) {
		if (K & 1) ret = ret * N % MOD;
		N = N * N % MOD;
		K >>= 1LL;
	}
	return ret;
}

ll Comb(ll N, ll K) {
	ll ret = IF[K];
	for (ll j = N; j > N - K; --j) ret = (ret * j) % MOD;
	return ret;
}

int main() {
	F[0] = IF[0] = 1;
	for (ll i = 1; i < MAX; ++i) {
		F[i] = F[i - 1] * i % MOD;
		IF[i] = Pow(F[i], MOD - 2);
	}

	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	vector<int> T;
	for (int i = 1; i <= N; ++i) {
		cin >> L[i] >> R[i];
		T.push_back(L[i]);
		T.push_back(R[i] + 1);
	}
	T.push_back(0);

	sort(T.begin(), T.end());
	T.erase(unique(T.begin(), T.end()), T.end());
	for (int i = 1; i <= N; ++i) {
		int l = lower_bound(T.begin(), T.end(), L[i]) - T.begin();
		int r = lower_bound(T.begin(), T.end(), R[i] + 1) - T.begin();
		for (int j = l; j < r; ++j) S[j].push_back(i);
	}

	all[0] = 1;
	for (int i = 1; i + 1 < T.size(); ++i) {
		memset(temp, 0, sizeof(temp));
		ll z = T[i + 1] - T[i];
		ll pv = 0, idx = 0;
		for (int a = 0; a < S[i].size(); ++a) C[a] = Comb(z + a, a + 1);

		for (int a = 0; a < S[i].size(); ++a) {
			while (idx < S[i][a]) pv = (pv + all[idx++]) % MOD;
			for (int b = a; b < S[i].size(); ++b) {
				temp[S[i][b]] = (temp[S[i][b]] + pv * C[b - a]) % MOD;
			}
			pv = 0;
		}
		for (int j = 0; j < MAX; ++j) all[j] = (all[j] + temp[j]) % MOD;
	}

	ll ans = accumulate(all + 1, all + MAX, 0LL) % MOD;
	cout << ans;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 1; i + 1 < T.size(); ++i) {
      |                  ~~~~~~^~~~~~~~~~
boat.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int a = 0; a < S[i].size(); ++a) C[a] = Comb(z + a, a + 1);
      |                   ~~^~~~~~~~~~~~~
boat.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int a = 0; a < S[i].size(); ++a) {
      |                   ~~^~~~~~~~~~~~~
boat.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int b = a; b < S[i].size(); ++b) {
      |                    ~~^~~~~~~~~~~~~

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