oj.uz

Submission #107030

# Submission time Handle Problem Language Result Execution time Memory
107030 2019-04-21T13:34:42 Z qoo2p5 Boat (APIO16_boat) C++17
0 / 100
 907 ms 6428 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, t) for (int i = s; i < t; i++)
#define per(i, s, t) for (int i = s; i >= t; i--)
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;

const int INF = (int) (1e9 + 1e6 + 123);

template<typename A, typename B> bool mini(A& x, const B& y) {
	if (y < x) {
		x = y;
		return true;
	}
	return false;
}

template<typename A, typename B> bool maxi(A& x, const B& y) {
	if (y > x) {
		x = y;
		return true;
	}
	return false;
}

void run();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	run();
	return 0;
}

const int N = 505;
const int MOD = 1000000000 + 7;

void add(int& x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
}

int power(int x, int y) {
	if (y == 0) {
		return 1;
	}
	if (y % 2 == 0) {
		return power(x * 1LL * x % MOD, y / 2);
	} else {
		return power(x, y - 1) * 1LL * x % MOD;
	}
}

int n;
int a[N], b[N];
vector<int> cool;

int fact[N];
int rfact[N];
int dp[2 * N][N];
int nxt[2 * N][N];
int prec[2 * N][N];

int cnk(int n, int k) {
	if (k > n) {
		return 0;
	}
	int res = 1;
	rep(i, 0, k) {
		res = res * 1LL * (n - i) % MOD;
	}
	res = res * 1LL * rfact[k] % MOD;
	return res;
}

void upd(int l, int r) {
	memcpy(nxt, dp, sizeof dp);

	int pref = 0;
	rep(block, 0, sz(cool)) {
		if (l <= block && block <= r) {
			add(nxt[block][1], pref);
		}
		rep(cnt, 0, N) {
			pref += dp[block][cnt];
		}
	}

	rep(block, 0, sz(cool)) {
		if (l <= block && block <= r) {
			int len = cool[block + 1] - cool[block];
			rep(cnt, 2, N) {
				add(nxt[block][cnt], nxt[block][cnt - 1] * 1LL * prec[block][cnt - 1] % MOD);
			}
		}
	}

	swap(nxt, dp);
}

void run() {
	cin >> n;
	rep(i, 0, n) {
		cin >> a[i] >> b[i];
		cool.push_back(a[i]);
		cool.push_back(b[i] + 1);
	}
	cool.push_back(0);
	sort(all(cool));
	cool.resize(unique(all(cool)) - cool.begin());
	cool.push_back(INF);

	fact[0] = 1;
	rep(i, 1, N) {
		fact[i] = fact[i - 1] * 1LL * i % MOD;
	}
	rep(i, 0, N) {
		rfact[i] = power(fact[i], MOD - 2);
	}

	rep(i, 0, sz(cool) - 1) {
		rep(x, 1, N) {
			int len = cool[i + 1] - cool[i];
			prec[i][x] = cnk(len, x + 1);
		}
	}

	dp[0][0] = 1;
	rep(i, 0, n) {
		int l = 0;
		while (cool[l] != a[i]) {
			l++;
		}
		int r = l;
		while (cool[r + 1] <= b[i]) {
			r++;
		}
		upd(l, r);
	}

	int ans = MOD - 1;
	rep(i, 0, 2 * N) {
		rep(j, 0, N) {
			add(ans, dp[i][j]);
		}
	}
	cout << ans << "\n";
}

Compilation message

boat.cpp: In function 'void upd(int, int)':
boat.cpp:99:8: warning: unused variable 'len' [-Wunused-variable]
    int len = cool[block + 1] - cool[block];
        ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 907 ms 6428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 907 ms 6428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 256 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 907 ms 6428 KB Output isn't correct
2 Halted 0 ms 0 KB -