Submission #479072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479072	2021-10-09T21:36:38 Z	arwaeystoamneg	Boat (APIO16_boat)	C++17	100 / 100	1108 ms	8388 KB

boat

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
//#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
//const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint() { v = 0; }
	mint(ll _v) {
		v = int((-MOD < _v&& _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mint& a, const mint& b) {
		return a.v == b.v;
	}
	friend bool operator!=(const mint& a, const mint& b) {
		return !(a == b);
	}
	friend bool operator<(const mint& a, const mint& b) {
		return a.v < b.v;
	}

	mint& operator+=(const mint& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this;
	}
	mint& operator-=(const mint& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this;
	}
	mint& operator*=(const mint& m) {
		v = int((ll)v * m.v % MOD); return *this;
	}
	mint& operator/=(const mint& m) { return (*this) *= inv(m); }
	friend mint power(mint a, ll p) {// MAKE SURE YOU ARE USING THE CORRECT VERSION OF POW!!!!!!!!
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	friend mint inv(const mint& a) {
		assert(a.v != 0);
		return power(a, MOD - 2);
	}

	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

typedef mint<inf, 5> mi; // 5 is primitive root for both common mods
typedef vector<mi> vmi;
int n;
vpi a;
vi order, sizes;
vpi b;
vmi fac, ifac;
vector<vmi>c;
mi choose(int x, int y)
{
	mi ans = 0, d = x;
	F0R(i, y)
	{
		if (i > x - 1)break;
		ans += d * fac[y - 1] * ifac[i] * ifac[i + 1] * ifac[y - i - 1];
		d *= (x - i - 1);
	}
	return ans;
}
int main()
{
	setIO("test1");
	cin >> n;
	ifac.rsz(n + 1);
	fac.rsz(n + 1);
	fac[0] = 1;
	F0R(i, n)
	{
		fac[i + 1] = (fac[i] * (i + 1));
	}
	F0R(i, n + 1)ifac[i] = inv(fac[i]);
	a.rsz(n);
	trav(x, a)cin >> x.f >> x.s, order.pb(x.f), order.pb(x.s);
	sort(all(order));
	vi temp;
	F0R(i, sz(order))
	{
		if (!sz(temp) || temp.back() != order[i])temp.pb(order[i]);
	}
	order = temp;
	F0R(i, sz(order))
	{
		sizes.pb(1);
		if (i < sz(order) - 1)sizes.pb(order[i + 1] - order[i] - 1);
	}
	b.rsz(n);
	F0R(i, n)
	{
		b[i].f = 2 * (lower_bound(all(order), a[i].f) - order.begin());
		b[i].s = 2 * (lower_bound(all(order), a[i].s) - order.begin());
	}
	vector<vmi>dp(n + 1, vmi(2 * sz(order)));
	F0R(i, n)dp[i][0] = 1;
	c.rsz(sz(sizes), vmi(n + 1, -1));
	F0R(i, n)
	{
		F0R(j, 2 * sz(order) - 1)
		{
			dp[i][j + 1] += dp[i][j];
			if (sizes[j] && b[i].f <= j && j <= b[i].s)
			{
				int co = 0;
				FOR(k, i + 1, n + 1)
				{
					if (b[k - 1].f <= j && j <= b[k - 1].s)co++;
					if (co)
					{
						mi c1 = c[j][co];
						if (c1 == -1)
						{
							c1 = choose(sizes[j], co);
							c[j][co] = c1;
						}
						dp[k][j + 1] += dp[i][j] * c1;
					}
				}
			}
		}
	}/*
	F0R(i, n + 1)
	{
		F0R(j, 2 * sz(order))
		{
			cerr << (int)dp[i][j] << " ";
		}
		cerr << endl;
	}*/
	mi ans = 0;
	F0R(i, 2 * sz(order))ans += dp[n][i];
	cout << (int)ans << endl;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4300 KB	Output is correct
2	Correct	6 ms	4300 KB	Output is correct
3	Correct	7 ms	4244 KB	Output is correct
4	Correct	6 ms	4300 KB	Output is correct
5	Correct	6 ms	4316 KB	Output is correct
6	Correct	6 ms	4300 KB	Output is correct
7	Correct	6 ms	4300 KB	Output is correct
8	Correct	7 ms	4312 KB	Output is correct
9	Correct	6 ms	4300 KB	Output is correct
10	Correct	7 ms	4300 KB	Output is correct
11	Correct	6 ms	4300 KB	Output is correct
12	Correct	6 ms	4300 KB	Output is correct
13	Correct	6 ms	4428 KB	Output is correct
14	Correct	6 ms	4300 KB	Output is correct
15	Correct	6 ms	4300 KB	Output is correct
16	Correct	3 ms	972 KB	Output is correct
17	Correct	2 ms	1100 KB	Output is correct
18	Correct	3 ms	972 KB	Output is correct
19	Correct	3 ms	1100 KB	Output is correct
20	Correct	3 ms	972 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4300 KB	Output is correct
2	Correct	6 ms	4300 KB	Output is correct
3	Correct	7 ms	4244 KB	Output is correct
4	Correct	6 ms	4300 KB	Output is correct
5	Correct	6 ms	4316 KB	Output is correct
6	Correct	6 ms	4300 KB	Output is correct
7	Correct	6 ms	4300 KB	Output is correct
8	Correct	7 ms	4312 KB	Output is correct
9	Correct	6 ms	4300 KB	Output is correct
10	Correct	7 ms	4300 KB	Output is correct
11	Correct	6 ms	4300 KB	Output is correct
12	Correct	6 ms	4300 KB	Output is correct
13	Correct	6 ms	4428 KB	Output is correct
14	Correct	6 ms	4300 KB	Output is correct
15	Correct	6 ms	4300 KB	Output is correct
16	Correct	3 ms	972 KB	Output is correct
17	Correct	2 ms	1100 KB	Output is correct
18	Correct	3 ms	972 KB	Output is correct
19	Correct	3 ms	1100 KB	Output is correct
20	Correct	3 ms	972 KB	Output is correct
21	Correct	449 ms	7608 KB	Output is correct
22	Correct	428 ms	7628 KB	Output is correct
23	Correct	415 ms	7500 KB	Output is correct
24	Correct	427 ms	7500 KB	Output is correct
25	Correct	453 ms	7452 KB	Output is correct
26	Correct	537 ms	7244 KB	Output is correct
27	Correct	511 ms	7416 KB	Output is correct
28	Correct	553 ms	7284 KB	Output is correct
29	Correct	531 ms	7244 KB	Output is correct
30	Correct	14 ms	7884 KB	Output is correct
31	Correct	13 ms	7756 KB	Output is correct
32	Correct	13 ms	7756 KB	Output is correct
33	Correct	13 ms	7800 KB	Output is correct
34	Correct	15 ms	7840 KB	Output is correct
35	Correct	8 ms	4284 KB	Output is correct
36	Correct	8 ms	4284 KB	Output is correct
37	Correct	9 ms	4324 KB	Output is correct
38	Correct	9 ms	4316 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	588 KB	Output is correct
2	Correct	5 ms	644 KB	Output is correct
3	Correct	7 ms	588 KB	Output is correct
4	Correct	6 ms	648 KB	Output is correct
5	Correct	7 ms	588 KB	Output is correct
6	Correct	10 ms	648 KB	Output is correct
7	Correct	10 ms	648 KB	Output is correct
8	Correct	10 ms	588 KB	Output is correct
9	Correct	10 ms	588 KB	Output is correct
10	Correct	10 ms	648 KB	Output is correct
11	Correct	8 ms	648 KB	Output is correct
12	Correct	6 ms	588 KB	Output is correct
13	Correct	8 ms	588 KB	Output is correct
14	Correct	7 ms	644 KB	Output is correct
15	Correct	7 ms	588 KB	Output is correct
16	Correct	4 ms	460 KB	Output is correct
17	Correct	3 ms	460 KB	Output is correct
18	Correct	3 ms	460 KB	Output is correct
19	Correct	3 ms	332 KB	Output is correct
20	Correct	3 ms	460 KB	Output is correct

Subtask #4
42.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4300 KB	Output is correct
2	Correct	6 ms	4300 KB	Output is correct
3	Correct	7 ms	4244 KB	Output is correct
4	Correct	6 ms	4300 KB	Output is correct
5	Correct	6 ms	4316 KB	Output is correct
6	Correct	6 ms	4300 KB	Output is correct
7	Correct	6 ms	4300 KB	Output is correct
8	Correct	7 ms	4312 KB	Output is correct
9	Correct	6 ms	4300 KB	Output is correct
10	Correct	7 ms	4300 KB	Output is correct
11	Correct	6 ms	4300 KB	Output is correct
12	Correct	6 ms	4300 KB	Output is correct
13	Correct	6 ms	4428 KB	Output is correct
14	Correct	6 ms	4300 KB	Output is correct
15	Correct	6 ms	4300 KB	Output is correct
16	Correct	3 ms	972 KB	Output is correct
17	Correct	2 ms	1100 KB	Output is correct
18	Correct	3 ms	972 KB	Output is correct
19	Correct	3 ms	1100 KB	Output is correct
20	Correct	3 ms	972 KB	Output is correct
21	Correct	449 ms	7608 KB	Output is correct
22	Correct	428 ms	7628 KB	Output is correct
23	Correct	415 ms	7500 KB	Output is correct
24	Correct	427 ms	7500 KB	Output is correct
25	Correct	453 ms	7452 KB	Output is correct
26	Correct	537 ms	7244 KB	Output is correct
27	Correct	511 ms	7416 KB	Output is correct
28	Correct	553 ms	7284 KB	Output is correct
29	Correct	531 ms	7244 KB	Output is correct
30	Correct	14 ms	7884 KB	Output is correct
31	Correct	13 ms	7756 KB	Output is correct
32	Correct	13 ms	7756 KB	Output is correct
33	Correct	13 ms	7800 KB	Output is correct
34	Correct	15 ms	7840 KB	Output is correct
35	Correct	8 ms	4284 KB	Output is correct
36	Correct	8 ms	4284 KB	Output is correct
37	Correct	9 ms	4324 KB	Output is correct
38	Correct	9 ms	4316 KB	Output is correct
39	Correct	7 ms	588 KB	Output is correct
40	Correct	5 ms	644 KB	Output is correct
41	Correct	7 ms	588 KB	Output is correct
42	Correct	6 ms	648 KB	Output is correct
43	Correct	7 ms	588 KB	Output is correct
44	Correct	10 ms	648 KB	Output is correct
45	Correct	10 ms	648 KB	Output is correct
46	Correct	10 ms	588 KB	Output is correct
47	Correct	10 ms	588 KB	Output is correct
48	Correct	10 ms	648 KB	Output is correct
49	Correct	8 ms	648 KB	Output is correct
50	Correct	6 ms	588 KB	Output is correct
51	Correct	8 ms	588 KB	Output is correct
52	Correct	7 ms	644 KB	Output is correct
53	Correct	7 ms	588 KB	Output is correct
54	Correct	4 ms	460 KB	Output is correct
55	Correct	3 ms	460 KB	Output is correct
56	Correct	3 ms	460 KB	Output is correct
57	Correct	3 ms	332 KB	Output is correct
58	Correct	3 ms	460 KB	Output is correct
59	Correct	704 ms	8268 KB	Output is correct
60	Correct	645 ms	8268 KB	Output is correct
61	Correct	633 ms	8268 KB	Output is correct
62	Correct	721 ms	8268 KB	Output is correct
63	Correct	650 ms	8272 KB	Output is correct
64	Correct	1072 ms	8268 KB	Output is correct
65	Correct	1108 ms	8388 KB	Output is correct
66	Correct	1089 ms	8268 KB	Output is correct
67	Correct	1094 ms	8268 KB	Output is correct
68	Correct	1107 ms	8268 KB	Output is correct
69	Correct	718 ms	8268 KB	Output is correct
70	Correct	728 ms	8268 KB	Output is correct
71	Correct	693 ms	8268 KB	Output is correct
72	Correct	733 ms	8268 KB	Output is correct
73	Correct	745 ms	8268 KB	Output is correct
74	Correct	76 ms	1100 KB	Output is correct
75	Correct	74 ms	1100 KB	Output is correct
76	Correct	78 ms	1152 KB	Output is correct
77	Correct	76 ms	1100 KB	Output is correct
78	Correct	77 ms	1144 KB	Output is correct

Submission #479072

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 42.0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
42.0 / 42.0