Submission #362538

#	Time	Username	Problem	Language	Result	Execution time	Memory
362538		flappybird	Boat (APIO16_boat)	C++14	31 / 100	857 ms	524292 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define MAX 1010101
#define all(v) v.begin(), v.end()
#define ln '\n'
#define MOD 1000000007
#define INF 210000000000
#define pb push_back
#define abs(x) (((x)>0)?(x):(-(x)))
#define len(x) ((x).second-(x).first)
typedef long long ll;
ll A[MAX], B[MAX];
vector<ll> v, num;
ll dp[MAX];
ll find(ll x) {
	ll l, r;
	l = 0;
	r = num.size();
	ll mid;
	while (l < r) {
		mid = (l + r) / 2;
		if (num[mid] == x) break;
		if (num[mid] > x) r = mid;
		if (num[mid] < x) l = mid + 1;
	}
	if (num[mid] == x) return mid;
	if (num[l] == x) return l;
	return -1;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll N;
	cin >> N;
	ll i, j, k;
	ll a, b;
	ll sum;
	dp[0] = 1;
	ll it;
	for (i = 1; i <= N; i++) {
		cin >> A[i] >> B[i];
		for (j = A[i]; j <= B[i]; j++) v.pb(j);
	}
	sort(all(v));
	v.push_back(MOD);
	num.pb(0);
	for (i = 0; i < v.size() - 1; i++) {
		if (v[i] != v[i + 1]) num.pb(v[i]);
	}
	ll sz = num.size();
	for (i = 1; i <= N; i++) {
		a = A[i];
		b = B[i];
		sum = 0;
		for (it = 0; it < sz; it++) {
			if (num[it] >= a) break;
			sum += dp[it];
			sum %= MOD;
		}
		it = find(a);
		for (j = it; j <= b - a + it; j++) {
			sum += dp[j];
			sum %= MOD;
			dp[j] = sum;
		}
	}
	sum = 0;
	for (it = 1; it < sz; it++) sum += dp[it], sum %= MOD;
	while (sum < 0) sum += MOD;
	cout << sum << ln;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:47:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (i = 0; i < v.size() - 1; i++) {
      |              ~~^~~~~~~~~~~~~~
boat.cpp:35:11: warning: unused variable 'k' [-Wunused-variable]
   35 |  ll i, j, k;
      |           ^
boat.cpp: In function 'll find(ll)':
boat.cpp:26:13: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  if (num[mid] == x) return mid;
      |             ^

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