oj.uz

Submission #479070

# Submission time Handle Problem Language Result Execution time Memory
479070 2021-10-09T21:26:08 Z arwaeystoamneg Boat (APIO16_boat) C++17
36 / 100
 2000 ms 7224 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 1321 ms 6108 KB Output is correct
2 Correct 1289 ms 6056 KB Output is correct
3 Correct 1317 ms 6048 KB Output is correct
4 Correct 1321 ms 6056 KB Output is correct
5 Correct 1304 ms 6000 KB Output is correct
6 Correct 1312 ms 7004 KB Output is correct
7 Correct 1257 ms 7068 KB Output is correct
8 Correct 1321 ms 7040 KB Output is correct
9 Correct 1272 ms 7148 KB Output is correct
10 Correct 1340 ms 7032 KB Output is correct
11 Correct 1300 ms 7224 KB Output is correct
12 Correct 1288 ms 6984 KB Output is correct
13 Correct 1301 ms 6988 KB Output is correct
14 Correct 1443 ms 7060 KB Output is correct
15 Correct 1306 ms 6984 KB Output is correct
16 Correct 234 ms 1372 KB Output is correct
17 Correct 252 ms 1368 KB Output is correct
18 Correct 264 ms 1496 KB Output is correct
19 Correct 265 ms 1488 KB Output is correct
20 Correct 246 ms 1356 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 6108 KB Output is correct
2 Correct 1289 ms 6056 KB Output is correct
3 Correct 1317 ms 6048 KB Output is correct
4 Correct 1321 ms 6056 KB Output is correct
5 Correct 1304 ms 6000 KB Output is correct
6 Correct 1312 ms 7004 KB Output is correct
7 Correct 1257 ms 7068 KB Output is correct
8 Correct 1321 ms 7040 KB Output is correct
9 Correct 1272 ms 7148 KB Output is correct
10 Correct 1340 ms 7032 KB Output is correct
11 Correct 1300 ms 7224 KB Output is correct
12 Correct 1288 ms 6984 KB Output is correct
13 Correct 1301 ms 6988 KB Output is correct
14 Correct 1443 ms 7060 KB Output is correct
15 Correct 1306 ms 6984 KB Output is correct
16 Correct 234 ms 1372 KB Output is correct
17 Correct 252 ms 1368 KB Output is correct
18 Correct 264 ms 1496 KB Output is correct
19 Correct 265 ms 1488 KB Output is correct
20 Correct 246 ms 1356 KB Output is correct
21 Execution timed out 2093 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 188 ms 852 KB Output is correct
2 Correct 159 ms 808 KB Output is correct
3 Correct 163 ms 844 KB Output is correct
4 Correct 165 ms 956 KB Output is correct
5 Correct 171 ms 732 KB Output is correct
6 Correct 258 ms 848 KB Output is correct
7 Correct 296 ms 860 KB Output is correct
8 Correct 270 ms 856 KB Output is correct
9 Correct 273 ms 816 KB Output is correct
10 Correct 265 ms 796 KB Output is correct
11 Correct 204 ms 940 KB Output is correct
12 Correct 166 ms 860 KB Output is correct
13 Correct 195 ms 800 KB Output is correct
14 Correct 193 ms 852 KB Output is correct
15 Correct 194 ms 920 KB Output is correct
16 Correct 80 ms 516 KB Output is correct
17 Correct 73 ms 460 KB Output is correct
18 Correct 71 ms 512 KB Output is correct
19 Correct 70 ms 516 KB Output is correct
20 Correct 86 ms 516 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 6108 KB Output is correct
2 Correct 1289 ms 6056 KB Output is correct
3 Correct 1317 ms 6048 KB Output is correct
4 Correct 1321 ms 6056 KB Output is correct
5 Correct 1304 ms 6000 KB Output is correct
6 Correct 1312 ms 7004 KB Output is correct
7 Correct 1257 ms 7068 KB Output is correct
8 Correct 1321 ms 7040 KB Output is correct
9 Correct 1272 ms 7148 KB Output is correct
10 Correct 1340 ms 7032 KB Output is correct
11 Correct 1300 ms 7224 KB Output is correct
12 Correct 1288 ms 6984 KB Output is correct
13 Correct 1301 ms 6988 KB Output is correct
14 Correct 1443 ms 7060 KB Output is correct
15 Correct 1306 ms 6984 KB Output is correct
16 Correct 234 ms 1372 KB Output is correct
17 Correct 252 ms 1368 KB Output is correct
18 Correct 264 ms 1496 KB Output is correct
19 Correct 265 ms 1488 KB Output is correct
20 Correct 246 ms 1356 KB Output is correct
21 Execution timed out 2093 ms 3916 KB Time limit exceeded
22 Halted 0 ms 0 KB -