Submission #362534

#	Time	Username	Problem	Language	Result	Execution time	Memory
362534		flappybird	Boat (APIO16_boat)	C++14	0 / 100	678 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;
int A[MAX], B[MAX];
vector<int> v, num;
int dp[MAX];
int find(int x) {
	int l, r;
	l = 1;
	r = num.size();
	int mid;
	while (l < r) {
		mid = (l + r) / 2;
		if (mid == x) break;
		if (mid > x) r = mid;
		if (mid < x) l = mid + 1;
	}
	if (mid == x) return mid;
	if (l == x) return l;
	return -1;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;
	int i, j, k;
	int a, b;
	int sum;
	dp[0] = 1;
	int 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]);
	}
	int 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: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (i = 0; i < v.size() - 1; i++) {
      |              ~~^~~~~~~~~~~~~~
boat.cpp:35:12: warning: unused variable 'k' [-Wunused-variable]
   35 |  int i, j, k;
      |            ^
boat.cpp: In function 'int find(int)':
boat.cpp:26:2: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  if (mid == x) return mid;
      |  ^~

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