Submission #261077

#	Time	Username	Problem	Language	Result	Execution time	Memory
261077		srvlt	Boat (APIO16_boat)	C++14	100 / 100	336 ms	8440 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1003, mod = 1e9 + 7;
int n, l[n0], r[n0], k, inv[n0];

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

int bp(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1)
			res = (ll)res * x % mod;
		x = (ll)x * x % mod;
		y /= 2;
	}
	return res;
}

struct Block {
	int l = 0, r = 0, t = 0;
	int val[n0], c[n0], cur = 0, last = 0;
	Block() {
		c[0] = 1;
	}
	void upd(int x) {
		val[t++] = x;
		c[t] = ((ll)c[t - 1] * (r - l + t) % mod) * inv[t] % mod;
		cur = last = 0;
		for (int i = 0; i < t; i++) {
			add(cur, (ll)c[t - i] * val[i] % mod);
			add(last, (ll)c[t - i - 1] * val[i] % mod);
		}
	}
};
Block b[n0];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	for (int i = 1; i < n0; i++)
		inv[i] = bp(i, mod - 2);
	cin >> n;
	vector <int> crd;
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i];
		r[i]++;
		crd.pb(l[i]), crd.pb(r[i]);
	}
	crd.pb(0), crd.pb(1);
	sort(all(crd));
	for (int i = 1; i < SZ(crd); i++) {
		if (crd[i - 1] < crd[i]) {
			b[k].l = crd[i - 1];
			b[k++].r = crd[i] - 1;
		}
	}
	b[0].upd(1);
	for (int i = 0; i < n; i++) {
		int cur = 0, j = 0;
		for (; j < k && b[j].r < l[i]; j++)
			add(cur, b[j].cur);
		for (; j < k && b[j].r < r[i]; j++) {
			b[j].upd(cur);
			cur = b[j].last;
		}
	}
	int res = 0;
	for (int i = 0; i < k; i++)
		add(res, b[i].cur);
	add(res, mod - 1);
	cout << res;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42