oj.uz

Submission #557708

# Submission time Handle Problem Language Result Execution time Memory
557708 2022-05-06T00:34:45 Z hhhhaura Boat (APIO16_boat) C++14
36 / 100
 2000 ms 16268 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;
	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;
	}
	int C(int n, int m) {
		if(n < m) return 0;
		return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
	}
	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));
		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;

	}

	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:79: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]
   79 |     if(l == a.size()) break;
      |        ~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1750 ms 16204 KB Output is correct
2 Correct 1794 ms 16204 KB Output is correct
3 Correct 1779 ms 16164 KB Output is correct
4 Correct 1816 ms 16160 KB Output is correct
5 Correct 1933 ms 16168 KB Output is correct
6 Correct 1740 ms 16144 KB Output is correct
7 Correct 1871 ms 16148 KB Output is correct
8 Correct 1772 ms 16148 KB Output is correct
9 Correct 1757 ms 16152 KB Output is correct
10 Correct 1866 ms 16144 KB Output is correct
11 Correct 1986 ms 16164 KB Output is correct
12 Correct 1869 ms 16084 KB Output is correct
13 Correct 1850 ms 16084 KB Output is correct
14 Correct 1882 ms 16152 KB Output is correct
15 Correct 1784 ms 16144 KB Output is correct
16 Correct 731 ms 16204 KB Output is correct
17 Correct 785 ms 16160 KB Output is correct
18 Correct 792 ms 16144 KB Output is correct
19 Correct 630 ms 16140 KB Output is correct
20 Correct 793 ms 16204 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1750 ms 16204 KB Output is correct
2 Correct 1794 ms 16204 KB Output is correct
3 Correct 1779 ms 16164 KB Output is correct
4 Correct 1816 ms 16160 KB Output is correct
5 Correct 1933 ms 16168 KB Output is correct
6 Correct 1740 ms 16144 KB Output is correct
7 Correct 1871 ms 16148 KB Output is correct
8 Correct 1772 ms 16148 KB Output is correct
9 Correct 1757 ms 16152 KB Output is correct
10 Correct 1866 ms 16144 KB Output is correct
11 Correct 1986 ms 16164 KB Output is correct
12 Correct 1869 ms 16084 KB Output is correct
13 Correct 1850 ms 16084 KB Output is correct
14 Correct 1882 ms 16152 KB Output is correct
15 Correct 1784 ms 16144 KB Output is correct
16 Correct 731 ms 16204 KB Output is correct
17 Correct 785 ms 16160 KB Output is correct
18 Correct 792 ms 16144 KB Output is correct
19 Correct 630 ms 16140 KB Output is correct
20 Correct 793 ms 16204 KB Output is correct
21 Correct 1812 ms 16148 KB Output is correct
22 Correct 1821 ms 16148 KB Output is correct
23 Correct 1778 ms 16204 KB Output is correct
24 Correct 1759 ms 16148 KB Output is correct
25 Correct 1778 ms 16148 KB Output is correct
26 Correct 1798 ms 16148 KB Output is correct
27 Correct 1811 ms 16268 KB Output is correct
28 Correct 1789 ms 16148 KB Output is correct
29 Correct 1795 ms 16152 KB Output is correct
30 Execution timed out 2071 ms 16084 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 980 KB Output is correct
2 Correct 256 ms 980 KB Output is correct
3 Correct 281 ms 980 KB Output is correct
4 Correct 283 ms 980 KB Output is correct
5 Correct 251 ms 964 KB Output is correct
6 Correct 168 ms 960 KB Output is correct
7 Correct 141 ms 960 KB Output is correct
8 Correct 148 ms 980 KB Output is correct
9 Correct 136 ms 980 KB Output is correct
10 Correct 214 ms 980 KB Output is correct
11 Correct 200 ms 980 KB Output is correct
12 Correct 184 ms 980 KB Output is correct
13 Correct 182 ms 960 KB Output is correct
14 Correct 378 ms 972 KB Output is correct
15 Correct 194 ms 980 KB Output is correct
16 Correct 372 ms 972 KB Output is correct
17 Correct 396 ms 852 KB Output is correct
18 Correct 478 ms 980 KB Output is correct
19 Correct 489 ms 852 KB Output is correct
20 Correct 499 ms 960 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1750 ms 16204 KB Output is correct
2 Correct 1794 ms 16204 KB Output is correct
3 Correct 1779 ms 16164 KB Output is correct
4 Correct 1816 ms 16160 KB Output is correct
5 Correct 1933 ms 16168 KB Output is correct
6 Correct 1740 ms 16144 KB Output is correct
7 Correct 1871 ms 16148 KB Output is correct
8 Correct 1772 ms 16148 KB Output is correct
9 Correct 1757 ms 16152 KB Output is correct
10 Correct 1866 ms 16144 KB Output is correct
11 Correct 1986 ms 16164 KB Output is correct
12 Correct 1869 ms 16084 KB Output is correct
13 Correct 1850 ms 16084 KB Output is correct
14 Correct 1882 ms 16152 KB Output is correct
15 Correct 1784 ms 16144 KB Output is correct
16 Correct 731 ms 16204 KB Output is correct
17 Correct 785 ms 16160 KB Output is correct
18 Correct 792 ms 16144 KB Output is correct
19 Correct 630 ms 16140 KB Output is correct
20 Correct 793 ms 16204 KB Output is correct
21 Correct 1812 ms 16148 KB Output is correct
22 Correct 1821 ms 16148 KB Output is correct
23 Correct 1778 ms 16204 KB Output is correct
24 Correct 1759 ms 16148 KB Output is correct
25 Correct 1778 ms 16148 KB Output is correct
26 Correct 1798 ms 16148 KB Output is correct
27 Correct 1811 ms 16268 KB Output is correct
28 Correct 1789 ms 16148 KB Output is correct
29 Correct 1795 ms 16152 KB Output is correct
30 Execution timed out 2071 ms 16084 KB Time limit exceeded
31 Halted 0 ms 0 KB -