Submission #107045

#	Time	Username	Problem	Language	Result	Execution time	Memory
107045		qoo2p5	Boat (APIO16_boat)	C++17	100 / 100	1246 ms	4584 KiB

boat

#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;
const long long MOD2 = MOD * 1LL * MOD;

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 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) {
	long long pref = 0;
	rep(block, 0, sz(cool)) {
		long long was = pref;
		rep(cnt, 0, N) {
			pref += dp[block][cnt] * 1LL * prec[block][cnt];
			if (pref >= MOD2) {
				pref -= MOD2;
			}
		}
		pref %= MOD;
		int len = cool[block + 1] - cool[block];
		if (l <= block && block <= r) {
			per(cnt, N - 1, 2) {
				add(dp[block][cnt], dp[block][cnt - 1]);
			}
			add(dp[block][1], was);
		}
	}
}

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) {
		int len = cool[i + 1] - cool[i];
		rep(j, 0, N) {
			prec[i][j] = cnk(len, j);
		}
	}

	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, sz(cool) - 1) {
		rep(j, 0, N) {
			add(ans, dp[i][j] * 1LL * prec[i][j] % MOD);
		}
	}
	cout << ans << "\n";
}

Compilation message (stderr)

boat.cpp: In function 'void upd(int, int)':
boat.cpp:95:7: warning: unused variable 'len' [-Wunused-variable]
   int len = cool[block + 1] - cool[block];
       ^~~

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