제출 #107016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107016		maksim_gaponov	Boat (APIO16_boat)	C++14	31 / 100	2037 ms	107964 KiB

boat

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

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0)
		x += MOD;
	return x;
}

const int MAXN = 1e9 + 10;

struct ST {
	unordered_map<int, int> f;
	int sum = 0;

	void add(int i, int x) {
		sum += x;
		sum %= MOD;
		for (; i < MAXN; i = ((i) | (i + 1))) {
			f[i] += x;
			f[i] %= MOD;
		}
	}

	int get(int r) {
		--r;
		int res = 0;
		for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
			res += f[i];
		return res % MOD;
	}
};

void run() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		// assert(a[i] == b[i]);
	}
	ST S;
	S.add(0, 1);
	for (int i = 0; i < n; ++i) {
		for (int j = b[i]; j >= a[i]; --j) {
			S.add(j, S.get(j));
		}
	}
	// vector<vector<int>> dp(n);
	// vector<int> dp0(n);
	// for (int i = 0; i < n; ++i) {
	// 	if (i == 0)
	// 		dp0[i] = 1;
	// 	else
	// 		dp0[i] = dp[i - 1].back();
	// 	dp[i].resize(b[i] - a[i] + 1);
	// 	for (int j = a[i]; j <= b[i]; ++j) {
	// 		dp[i][j - a[i]] = 1;
	// 		if (j != a[i]) {
	// 			dp[i][j - a[i]] += dp[i][j - a[i] - 1];
	// 		} else {
	// 			dp[i][j - a[i]] += dp0[i];
	// 		}
	// 		// if (i > 0) {
	// 		// 	dp[i][j - a[i]] += dp[i - 1][j - 1 - a[i - 1]]
	// 		// }
	// 		if (i > 0) {
	// 			int val = 0;
	// 			if (j - 1 >= a[i - 1]) {
	// 				if (j - 1 > b[i - 1])
	// 					val = dp[i - 1].back();
	// 				else
	// 					val = dp[i - 1][j - a[i - 1] - 1];
	// 			}
	// 			else {
	// 				val = dp0[i - 1];
	// 			}
	// 			dp[i][j - a[i]] += val;
	// 		} else {
	// 			dp[i][j - a[i]] += 1;
	// 		}
	// 		dp[i][j - a[i]] %= MOD;
	// 	}
	// }
	int ans = S.sum;
	ans--;
	ans = mod(ans);
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

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