oj.uz

Submission #109367

# Submission time Handle Problem Language Result Execution time Memory
109367 2019-05-06T09:44:06 Z b2563125 Boat (APIO16_boat) C++14
9 / 100
 924 ms 13176 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int __int128
#define vel vector<long long>
#define V vector
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
int pr = 1000000007;
void uni(vel &a) {
	vel ans(1, a[0]);
	int n = a.size();
	rep(i,n - 1) { if (a[i + 1] != a[i]) { ans.push_back(a[i + 1]); } }
	a = ans;
}
int rui(int a, int n) {
	if (n == 0) { return 1; }
	int back = rui(a, n / 2);
	back *= back; back %= pr;
	if (n % 2 == 0) { return back; }
	return (back*a) % pr;
}
int inv(int a) {
	return rui(a, pr - 2);
}
signed main() {
	signed n; cin >> n;
	vel a(n);
	vel b(n);
	vel all_time(1, 0);
	rep(i, n) {
		cin >> a[i] >> b[i]; b[i]++;
		all_time.push_back(a[i]);
		all_time.push_back(b[i]);
	}
	sort(all_time.begin(), all_time.end());
	uni(all_time);
	int sz = all_time.size();
	vel gap(sz - 1);
	rep(i, sz - 1) { gap[i] = all_time[i + 1] - all_time[i]; }
	vel count(sz-1);
	rep(i, n) {
		a[i] = lower_bound(all_time.begin(), all_time.end(), a[i])-all_time.begin();
		b[i] = lower_bound(all_time.begin(), all_time.end(), b[i])-all_time.begin();
		rep(j, b[i] - a[i]) {
			count[a[i] + j]++;
		}
	}
	V<vel> com(sz-1);
	rep(i, sz-1) {
		int ba = 1;
		rep(j, count[i]) {
			ba *= gap[i] - j; ba %= pr;
			ba *= inv(j + 1); ba %= pr;
			com[i].push_back(ba);
		}
	}
	V<V<vel>> dp1(2, V<vel>(sz-1,vel(n)));
	vel now_count(sz - 1, 0);
	rep(i, n) {
		int now = i % 2;
		int nex = (i + 1) % 2;
		dp1[nex] = dp1[now];
		int sum = 1;
		rep(j, a[i]) {
			rep(k, now_count[j]) {
				sum += dp1[now][j][k] * com[j][k];
			}
		}
		for (int j = a[i]; j < b[i]; j++) {
			dp1[nex][j][0] += sum; dp1[nex][j][0] %= pr;
			rep(k, now_count[j]) {
				dp1[nex][j][k + 1] += dp1[now][j][k]; dp1[nex][j][k + 1] %= pr;
				sum += dp1[now][j][k] * com[j][k];
			}
			sum += dp1[now][j][now_count[j]] * com[j][now_count[j]];
			sum %= pr;
			now_count[j]++;
		}
	}
	ll ans = 0;
	rep(i, sz-1) {
		rep(k, count[i]) {
			ans += dp1[n%2][i][k] * com[i][k];
			ans %= pr;
		}
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 12408 KB Output is correct
2 Correct 218 ms 12288 KB Output is correct
3 Correct 202 ms 12288 KB Output is correct
4 Correct 223 ms 12276 KB Output is correct
5 Correct 171 ms 12324 KB Output is correct
6 Correct 200 ms 12416 KB Output is correct
7 Correct 195 ms 12288 KB Output is correct
8 Correct 234 ms 12408 KB Output is correct
9 Correct 204 ms 12408 KB Output is correct
10 Correct 225 ms 12288 KB Output is correct
11 Correct 195 ms 12288 KB Output is correct
12 Correct 205 ms 12408 KB Output is correct
13 Correct 202 ms 12288 KB Output is correct
14 Correct 207 ms 12288 KB Output is correct
15 Correct 200 ms 12408 KB Output is correct
16 Correct 34 ms 2432 KB Output is correct
17 Correct 38 ms 2688 KB Output is correct
18 Correct 36 ms 2560 KB Output is correct
19 Correct 35 ms 2680 KB Output is correct
20 Correct 36 ms 2588 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 12408 KB Output is correct
2 Correct 218 ms 12288 KB Output is correct
3 Correct 202 ms 12288 KB Output is correct
4 Correct 223 ms 12276 KB Output is correct
5 Correct 171 ms 12324 KB Output is correct
6 Correct 200 ms 12416 KB Output is correct
7 Correct 195 ms 12288 KB Output is correct
8 Correct 234 ms 12408 KB Output is correct
9 Correct 204 ms 12408 KB Output is correct
10 Correct 225 ms 12288 KB Output is correct
11 Correct 195 ms 12288 KB Output is correct
12 Correct 205 ms 12408 KB Output is correct
13 Correct 202 ms 12288 KB Output is correct
14 Correct 207 ms 12288 KB Output is correct
15 Correct 200 ms 12408 KB Output is correct
16 Correct 34 ms 2432 KB Output is correct
17 Correct 38 ms 2688 KB Output is correct
18 Correct 36 ms 2560 KB Output is correct
19 Correct 35 ms 2680 KB Output is correct
20 Correct 36 ms 2588 KB Output is correct
21 Correct 795 ms 12940 KB Output is correct
22 Incorrect 924 ms 13176 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 12408 KB Output is correct
2 Correct 218 ms 12288 KB Output is correct
3 Correct 202 ms 12288 KB Output is correct
4 Correct 223 ms 12276 KB Output is correct
5 Correct 171 ms 12324 KB Output is correct
6 Correct 200 ms 12416 KB Output is correct
7 Correct 195 ms 12288 KB Output is correct
8 Correct 234 ms 12408 KB Output is correct
9 Correct 204 ms 12408 KB Output is correct
10 Correct 225 ms 12288 KB Output is correct
11 Correct 195 ms 12288 KB Output is correct
12 Correct 205 ms 12408 KB Output is correct
13 Correct 202 ms 12288 KB Output is correct
14 Correct 207 ms 12288 KB Output is correct
15 Correct 200 ms 12408 KB Output is correct
16 Correct 34 ms 2432 KB Output is correct
17 Correct 38 ms 2688 KB Output is correct
18 Correct 36 ms 2560 KB Output is correct
19 Correct 35 ms 2680 KB Output is correct
20 Correct 36 ms 2588 KB Output is correct
21 Correct 795 ms 12940 KB Output is correct
22 Incorrect 924 ms 13176 KB Output isn't correct
23 Halted 0 ms 0 KB -