oj.uz

Submission #362535

# Submission time Handle Problem Language Result Execution time Memory
362535 2021-02-03T15:04:36 Z flappybird Boat (APIO16_boat) C++14
0 / 100
 560 ms 524292 KB 
#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 = 1;
	r = num.size();
	ll 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);
	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

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:2: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  if (mid == x) return mid;
      |  ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 560 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -