Submission #1359718

#TimeUsernameProblemLanguageResultExecution timeMemory
1359718blackscreen1Boat (APIO16_boat)C++20
9 / 100
299 ms54828 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, prv = 0, dp[505][1005], dp2[505][1005], cr, sz[1005];
ll ch[3005][3005];
pll a[505], b[505];
set<ll> st;
vector<pll> rngs;
vector<ll> cs;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	iloop(0, n) {
		cin >> a[i].first >> a[i].second;
		st.insert(a[i].first);
		st.insert(a[i].second);
	}
	iloop(0, 3005) jloop(0, 3005) {
		if (i < j) continue;
		if (i == 0 || i == j) {ch[i][j] = 1; continue;}
		ch[i][j] = (ch[i-1][j] + ch[i-1][j-1])%MOD1;
	}
	for (auto it : st) {
		if (prv && prv+1 < it) rngs.push_back({prv+1, it-1}), cs.push_back(prv+1);
		rngs.push_back({it, it}), cs.push_back(it);
		prv = it;
	}
	m = rngs.size();
	iloop(0, m) sz[i] = rngs[i].second - rngs[i].first + 1;
	iloop(0, n) {
		b[i].first = lower_bound(cs.begin(), cs.end(), a[i].first) - cs.begin();
		b[i].second = upper_bound(cs.begin(), cs.end(), a[i].second) - cs.begin() - 1;
	}
	iloop(0, n) {
		jloop(0, m) dp[i][j] = 0;
		jloop(b[i].second, b[i].first-1) {
			cr = 1;
			dp[i][j] += sz[j];
			kloop(i-1, -1) {
				if (j) dp[i][j] += dp2[k][j-1] * ch[sz[j]+cr-1][sz[j]-1];
				if (b[k].first <= j && b[k].second >= j) cr++;
				dp[i][j] %= MOD1;
			}
		}
		jloop(0, m) dp2[i][j] = (dp[i][j] + (j ? dp2[i][j-1] : 0))%MOD1;
	}
	ll cans = 0;
	iloop(0, n) jloop(0, m) {cans += dp[i][j]; cans %= MOD1;}
	cout << cans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...