oj.uz

Submission #307646

# Submission time Handle Problem Language Result Execution time Memory
307646 2020-09-28T22:59:01 Z CodeTiger927 Boat (APIO16_boat) C++14
0 / 100
 4 ms 2432 KB 
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 <= MAXN) {
		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] += (curR - curL + 1);
			if(dp[i][j] >= MOD) dp[i][j] -= MOD;
			cnt[j] += dp[i][j];
			if(cnt[j] >= MOD) cnt[j] -= MOD;
			// cout << i << " " << j << " " << dp[i][j] << endl;
			update(j,dp[i][j]);

			ans += dp[i][j];
			if(ans >= MOD) ans -= MOD;
		}
	}
	// for(int i = 0;i < v.size();++i) {
	// 	cout << v[i] << endl;
	// }
	cout << ans << endl;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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