Submission #307635

#	Time	Username	Problem	Language	Result	Execution time	Memory
307635		CodeTiger927	Boat (APIO16_boat)	C++14	0 / 100	3 ms	2432 KiB

boat

using namespace std;

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define MAXN 505
#define MOD 1000000007

long long qa[MAXN],qb[MAXN],cnt[3 * MAXN],bit[12 * MAXN],dp[MAXN][3 * MAXN];
int N;

void update(int x,int v) {
	++x;
	while(x <= N) {
		bit[x] += v;
		if(bit[x] >= MOD) bit[x] -= MOD;
		x += x & (-x);
	}
}

long long getSum(int x) {
	long long res = 0;
	++x;
	while(x > 0) {
		res += bit[x];
		if(res >= MOD) res -= MOD;
		x -= x & (-x);
	}
	return res;
}

// long long inv(long long a, long long b){
// 	return 1 < a ? b - inv(b % a,a) * b / a : 1;
// }

// long long inv(long long a) {
// 	return inv(a,MOD);
// }

int main() {
	cin >> N;

	set<int> s;
	vector<int> v;

	for(int i = 0;i < N;++i) {
		cin >> qa[i] >> qb[i];
		s.insert(qa[i]);
		s.insert(qb[i]);
		s.insert(qb[i] + 1);
	}
	for(auto itr = s.begin();itr != s.end();++itr) {
		v.push_back(*(itr));
	}

	long long ans = 0;

	for(int i = 0;i < N;++i) {
		for(int j = v.size() - 2;j >= 0;--j) {
			int curL = v[j];
			int curR = v[j + 1] - 1;
			if(curL > qb[i] || curR < qa[i]) continue;
			dp[i][j] += (getSum(j - 1) * (curR - curL + 1)) % MOD;
			if(dp[i][j] >= MOD) dp[i][j] -= MOD;
			dp[i][j] += ((cnt[j] * (curR - curL) % MOD) * 500000004) % MOD;
			if(dp[i][j] >= MOD) dp[i][j] -= MOD;
			++dp[i][j];
			if(dp[i][j] == MOD) dp[i][j] -= MOD;
			cnt[j] += dp[i][j];
			if(cnt[j] >= MOD) cnt[j] -= MOD;
			update(j,dp[i][j]);

			ans += dp[i][j];
			if(ans >= MOD) ans -= MOD;
		}
	}
	cout << ans << endl;
}

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