oj.uz

답안 #557709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557709 2022-05-06T00:38:55 Z hhhhaura Boat (APIO16_boat) C++14
36 / 100
 2000 ms 18228 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
namespace solver {
	int n, tot;
	vector<pii> seg;
	vector<int> v, fac, inv;
	vector<vector<int>> dp, pre, P, cal, C;
	int pow_(int a, int times) {
		int ans = 1;
		for(; times > 0; times >>= 1, a = a * a % MOD) {
			if(times & 1) ans = ans * a % MOD;
		}
		return ans;
	}
	void init_(int _n) {
		n = _n;
		v.clear();
		seg.assign(n + 1, {0, 0});
		dp.assign(n + 1, vector<int>(n * 2 + 1, 0));
		pre.assign(n + 1, vector<int>(n * 2 + 1, 0));
		P.assign(n * 2 + 1, vector<int>(n + 1, 0));
		C.assign(n + 1, vector<int>(n + 1, 0));
		cal.assign(n * 2 + 1, vector<int>(n + 1, 0));
		fac.assign(n + 1, 1);
		inv.assign(n + 1, 1);
		rep(i, 1, n) fac[i] = fac[i - 1] * i % MOD;
		inv[n] = pow_(fac[n], MOD - 2);
		rrep(i, 1, n - 1) inv[i] = inv[i + 1] * (i + 1) % MOD;
		rep(i, 0, n) rep(j, 0, i) {
			C[i][j] = fac[i] * inv[j] % MOD * inv[i - j] % MOD;
		}
	}

	void solve() {
		sort(all(v));
		v.resize(unique(all(v)) - v.begin());
		tot = v.size() - 1;
		rep(i, 1, n) {
			int L = seg[i].x, R = seg[i].y;
			L = lower_bound(all(v), L) - v.begin() + 1;
			R = lower_bound(all(v), R + 1) - v.begin();
			seg[i] = {L, R};
		}
		vector<int> a, b;
		rep(i, 1, signed(v.size()) - 1) a.push_back(v[i] - v[i - 1]);
		sort(all(a)), a.resize(unique(all(a)) - a.begin());
		int l = 0, cur = 1;
		rep(i, 1, 1000000000) {
			cur = cur * i % MOD;
			if(a[l] == i) {
				b.push_back(cur), l++;
				if(l == a.size()) break;
			}
		}
		rep(i, 1, tot) {
			int len = v[i] - v[i - 1];
			int id = lower_bound(all(a), len) - a.begin();
			rep(j, 1, n) {
				int cur = 1;
				rep(k, 0, j - 1) cur = cur * (len - k) % MOD;
				cur = pow_(b[id], MOD - 2) * cur % MOD;
				if(len < j) P[i][j] = 0;
				else P[i][j] = b[id] * cur % MOD * inv[j] % MOD;
			}
		}
		rep(i, 1, tot) rep(j, 1, n) {
			rep(k, 1, j) {
				cal[i][j] += P[i][k] * C[j - 1][k - 1] % MOD;
				cal[i][j] %= MOD;
			}
		}
		dp[0][0] = 1;
		rep(i, 0, tot) pre[0][i] = 1;
		rep(i, 1, n) {
			int L = seg[i].x, R = seg[i].y;
			rep(j, 1, tot) if(L <= j && j <= R) {
				int cnt = 0;
				rrep(k, 0, i - 1) {
					cnt += (seg[k + 1].x <= j && seg[k + 1].y >= j);
					dp[i][j] += pre[k][j - 1] * cal[j][cnt] % MOD;
					dp[i][j] %= MOD;
				}
			}
			rep(j, 1, tot) pre[i][j] = (pre[i][j - 1] + dp[i][j]) % MOD;
		}
		int ans = 0;
		rep(i, 1, n) ans = (ans + pre[i][tot]) % MOD;
		cout << ans << "\n";
	}
	
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n; cin >> n;
	init_(n);
	rep(i, 1, n) {
		cin >> seg[i].x >> seg[i].y;
		v.push_back(seg[i].x);
		v.push_back(seg[i].y + 1);
	}
	solve();
	return 0;
}

Compilation message

boat.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
boat.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
boat.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~
boat.cpp: In function 'void solver::solve()':
boat.cpp:78:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     if(l == a.size()) break;
      |        ~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1352 ms 18132 KB Output is correct
2 Correct 1386 ms 18132 KB Output is correct
3 Correct 1379 ms 18132 KB Output is correct
4 Correct 1405 ms 18132 KB Output is correct
5 Correct 1511 ms 18116 KB Output is correct
6 Correct 1317 ms 18132 KB Output is correct
7 Correct 1452 ms 18132 KB Output is correct
8 Correct 1311 ms 18132 KB Output is correct
9 Correct 1342 ms 18124 KB Output is correct
10 Correct 1473 ms 18228 KB Output is correct
11 Correct 1581 ms 18132 KB Output is correct
12 Correct 1436 ms 18132 KB Output is correct
13 Correct 1407 ms 18132 KB Output is correct
14 Correct 1465 ms 18112 KB Output is correct
15 Correct 1343 ms 18124 KB Output is correct
16 Correct 649 ms 18112 KB Output is correct
17 Correct 698 ms 18132 KB Output is correct
18 Correct 730 ms 18112 KB Output is correct
19 Correct 554 ms 18124 KB Output is correct
20 Correct 737 ms 18124 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1352 ms 18132 KB Output is correct
2 Correct 1386 ms 18132 KB Output is correct
3 Correct 1379 ms 18132 KB Output is correct
4 Correct 1405 ms 18132 KB Output is correct
5 Correct 1511 ms 18116 KB Output is correct
6 Correct 1317 ms 18132 KB Output is correct
7 Correct 1452 ms 18132 KB Output is correct
8 Correct 1311 ms 18132 KB Output is correct
9 Correct 1342 ms 18124 KB Output is correct
10 Correct 1473 ms 18228 KB Output is correct
11 Correct 1581 ms 18132 KB Output is correct
12 Correct 1436 ms 18132 KB Output is correct
13 Correct 1407 ms 18132 KB Output is correct
14 Correct 1465 ms 18112 KB Output is correct
15 Correct 1343 ms 18124 KB Output is correct
16 Correct 649 ms 18112 KB Output is correct
17 Correct 698 ms 18132 KB Output is correct
18 Correct 730 ms 18112 KB Output is correct
19 Correct 554 ms 18124 KB Output is correct
20 Correct 737 ms 18124 KB Output is correct
21 Correct 1424 ms 18132 KB Output is correct
22 Correct 1419 ms 18116 KB Output is correct
23 Correct 1390 ms 18132 KB Output is correct
24 Correct 1379 ms 18132 KB Output is correct
25 Correct 1394 ms 18132 KB Output is correct
26 Correct 1425 ms 18132 KB Output is correct
27 Correct 1453 ms 18136 KB Output is correct
28 Correct 1437 ms 18112 KB Output is correct
29 Correct 1417 ms 18004 KB Output is correct
30 Execution timed out 2085 ms 18132 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 1048 KB Output is correct
2 Correct 252 ms 1044 KB Output is correct
3 Correct 281 ms 1048 KB Output is correct
4 Correct 270 ms 1048 KB Output is correct
5 Correct 244 ms 1044 KB Output is correct
6 Correct 166 ms 1060 KB Output is correct
7 Correct 134 ms 1048 KB Output is correct
8 Correct 146 ms 1044 KB Output is correct
9 Correct 133 ms 1048 KB Output is correct
10 Correct 214 ms 1056 KB Output is correct
11 Correct 195 ms 980 KB Output is correct
12 Correct 180 ms 1044 KB Output is correct
13 Correct 186 ms 1100 KB Output is correct
14 Correct 367 ms 1100 KB Output is correct
15 Correct 190 ms 980 KB Output is correct
16 Correct 376 ms 1044 KB Output is correct
17 Correct 386 ms 980 KB Output is correct
18 Correct 493 ms 1044 KB Output is correct
19 Correct 472 ms 1044 KB Output is correct
20 Correct 499 ms 980 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1352 ms 18132 KB Output is correct
2 Correct 1386 ms 18132 KB Output is correct
3 Correct 1379 ms 18132 KB Output is correct
4 Correct 1405 ms 18132 KB Output is correct
5 Correct 1511 ms 18116 KB Output is correct
6 Correct 1317 ms 18132 KB Output is correct
7 Correct 1452 ms 18132 KB Output is correct
8 Correct 1311 ms 18132 KB Output is correct
9 Correct 1342 ms 18124 KB Output is correct
10 Correct 1473 ms 18228 KB Output is correct
11 Correct 1581 ms 18132 KB Output is correct
12 Correct 1436 ms 18132 KB Output is correct
13 Correct 1407 ms 18132 KB Output is correct
14 Correct 1465 ms 18112 KB Output is correct
15 Correct 1343 ms 18124 KB Output is correct
16 Correct 649 ms 18112 KB Output is correct
17 Correct 698 ms 18132 KB Output is correct
18 Correct 730 ms 18112 KB Output is correct
19 Correct 554 ms 18124 KB Output is correct
20 Correct 737 ms 18124 KB Output is correct
21 Correct 1424 ms 18132 KB Output is correct
22 Correct 1419 ms 18116 KB Output is correct
23 Correct 1390 ms 18132 KB Output is correct
24 Correct 1379 ms 18132 KB Output is correct
25 Correct 1394 ms 18132 KB Output is correct
26 Correct 1425 ms 18132 KB Output is correct
27 Correct 1453 ms 18136 KB Output is correct
28 Correct 1437 ms 18112 KB Output is correct
29 Correct 1417 ms 18004 KB Output is correct
30 Execution timed out 2085 ms 18132 KB Time limit exceeded
31 Halted 0 ms 0 KB -