Submission #401493

#	Time	Username	Problem	Language	Result	Execution time	Memory
401493		BERNARB01	Boat (APIO16_boat)	C++17	31 / 100	565 ms	524292 KiB

boat

#include <bits/stdc++.h>

using namespace std;

const int mod = (int) 1e9 + 7;

template<typename T>
class segtree {
private:
	int b;
	vector<T> tr;
public:
	segtree() {}
	segtree(int n) {
		b = 1;
		while (b < n) {
			b <<= 1;
		}
		tr.assign(2 * b, 0);
	}
	void upd(int i, const T& val) {
		tr[i += b] = val;
		for (i >>= 1; i > 0; i >>= 1) {
			tr[i] = (tr[i << 1] + tr[i << 1 | 1]) % mod;
		}
	}
	T qry(int l, int r) {
		T ans = 0;
		for (l += b, r += b; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) ans = (ans + tr[l++]) % mod;
			if (!(r & 1)) ans = (ans + tr[r--]) % mod;
		}
		return ans;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n), b(n), se;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		for (int j = a[i]; j <= b[i]; j++) {
			se.push_back(j);
		}
	}
	sort(se.begin(), se.end());
	int idd = 1;
	map<int, int> mp;
	for (int i = 0; i < (int) se.size(); i++) {
		if (i == 0 || se[i] != se[i - 1]) {
			mp[se[i]] = idd++;
		}
	}
	for (int i = 0; i < n; i++) {
		a[i] = mp[a[i]];
		b[i] = mp[b[i]];
	}
	segtree<long long> st(idd);
	vector<long long> dp(idd, 0);
	dp[0] = 1;
	st.upd(0, 1);
	for (int i = 0; i < n; i++) {
		for (int j = b[i]; j >= a[i]; j--) {
			dp[j] = (dp[j] + st.qry(0, j - 1)) % mod;
			st.upd(j, dp[j]);
		}
	}
	long long sum = 0;
	for (int i = 1; i < idd; i++) {
		sum = (sum + dp[i]) % mod;
	}
	cout << sum << '\n';
	return 0;
}

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