Submission #261074

#	Time	Username	Problem	Language	Result	Execution time	Memory
261074		srvlt	Boat (APIO16_boat)	C++14	100 / 100	323 ms	8448 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;

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 Mint {
	int b = 0;
	Mint(int x = 0) {
		b = x;
		if (b >= mod) b -= mod;
	}
	void operator += (const Mint & x) {
		b += x.b;
		if (b >= mod) b -= mod;
	}
	Mint operator + (const Mint & x) const {
		Mint res = * this;
		res += x;
		return res;
	}
	Mint operator * (const Mint & x) const {
		Mint res;
		res.b = (ll)b * x.b % mod;
		return res;
	}
	Mint operator / (const Mint & x) const {
		Mint res;
		res.b = (ll)b * bp(x.b, mod - 2) % mod;
		return res;
	}
};

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

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	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++) {
		Mint cur;
		int j = 0;
		for (; j < k && b[j].r < l[i]; j++)
			cur += b[j].cur;
		for (; j < k && b[j].r < r[i]; j++) {
			b[j].upd(cur);
			cur = b[j].last;
		}
	}
	Mint res;
	for (int i = 0; i < k; i++)
		res += b[i].cur;
	res += (mod - 1);
	cout << res.b;
}

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