oj.uz

Submission #479071

# Submission time Handle Problem Language Result Execution time Memory
479071 2021-10-09T21:26:55 Z arwaeystoamneg Boat (APIO16_boat) C++17
36 / 100
 2000 ms 3916 KB 
// 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;
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;
	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)
					{
						dp[k][j + 1] += dp[i][j] * choose(sizes[j], co);
					}
				}
			}
		}
	}/*
	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 7 ms 2252 KB Output is correct
2 Correct 10 ms 2252 KB Output is correct
3 Correct 7 ms 2252 KB Output is correct
4 Correct 9 ms 2252 KB Output is correct
5 Correct 7 ms 2324 KB Output is correct
6 Correct 7 ms 2252 KB Output is correct
7 Correct 8 ms 2252 KB Output is correct
8 Correct 7 ms 2252 KB Output is correct
9 Correct 7 ms 2252 KB Output is correct
10 Correct 6 ms 2252 KB Output is correct
11 Correct 6 ms 2252 KB Output is correct
12 Correct 6 ms 2380 KB Output is correct
13 Correct 8 ms 2252 KB Output is correct
14 Correct 7 ms 2324 KB Output is correct
15 Correct 6 ms 2252 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 588 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 5 ms 588 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2252 KB Output is correct
2 Correct 10 ms 2252 KB Output is correct
3 Correct 7 ms 2252 KB Output is correct
4 Correct 9 ms 2252 KB Output is correct
5 Correct 7 ms 2324 KB Output is correct
6 Correct 7 ms 2252 KB Output is correct
7 Correct 8 ms 2252 KB Output is correct
8 Correct 7 ms 2252 KB Output is correct
9 Correct 7 ms 2252 KB Output is correct
10 Correct 6 ms 2252 KB Output is correct
11 Correct 6 ms 2252 KB Output is correct
12 Correct 6 ms 2380 KB Output is correct
13 Correct 8 ms 2252 KB Output is correct
14 Correct 7 ms 2324 KB Output is correct
15 Correct 6 ms 2252 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 588 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 5 ms 588 KB Output is correct
21 Execution timed out 2078 ms 3916 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 460 KB Output is correct
2 Correct 47 ms 460 KB Output is correct
3 Correct 67 ms 460 KB Output is correct
4 Correct 62 ms 460 KB Output is correct
5 Correct 72 ms 460 KB Output is correct
6 Correct 157 ms 460 KB Output is correct
7 Correct 159 ms 460 KB Output is correct
8 Correct 158 ms 460 KB Output is correct
9 Correct 166 ms 464 KB Output is correct
10 Correct 160 ms 464 KB Output is correct
11 Correct 90 ms 460 KB Output is correct
12 Correct 65 ms 468 KB Output is correct
13 Correct 97 ms 460 KB Output is correct
14 Correct 89 ms 460 KB Output is correct
15 Correct 87 ms 460 KB Output is correct
16 Correct 35 ms 332 KB Output is correct
17 Correct 32 ms 388 KB Output is correct
18 Correct 28 ms 332 KB Output is correct
19 Correct 25 ms 392 KB Output is correct
20 Correct 33 ms 384 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2252 KB Output is correct
2 Correct 10 ms 2252 KB Output is correct
3 Correct 7 ms 2252 KB Output is correct
4 Correct 9 ms 2252 KB Output is correct
5 Correct 7 ms 2324 KB Output is correct
6 Correct 7 ms 2252 KB Output is correct
7 Correct 8 ms 2252 KB Output is correct
8 Correct 7 ms 2252 KB Output is correct
9 Correct 7 ms 2252 KB Output is correct
10 Correct 6 ms 2252 KB Output is correct
11 Correct 6 ms 2252 KB Output is correct
12 Correct 6 ms 2380 KB Output is correct
13 Correct 8 ms 2252 KB Output is correct
14 Correct 7 ms 2324 KB Output is correct
15 Correct 6 ms 2252 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 4 ms 588 KB Output is correct
19 Correct 4 ms 716 KB Output is correct
20 Correct 5 ms 588 KB Output is correct
21 Execution timed out 2078 ms 3916 KB Time limit exceeded
22 Halted 0 ms 0 KB -