ilovehitagi's blog

By ilovehitagi, history, 3 years ago, In English

Editorial hinted that there is a $$$O(n^2.log(n))$$$ solution so I tried to implement so using BIT. Turns out I'm still getting TLE, in fact its even slower than the $$$O(n^3)$$$ for some reason.

Code
  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just use dp (note: MI = modint)

int n;
cin >> n;
vector<MI> dp(3001);
dp[0] = 1;
vector<int> x(n), y(n);
for(int& i : x)
	cin >> i;
for(int& i : y)
	cin >> i;
for(int i = 0; i < n; ++i) {
	int a = x[i], b = y[i];
	for(int j = 1; j < 3001; ++j)
		dp[j] += dp[j - 1];
	for(int j = 0; j < a; ++j)
		dp[j] = 0;
	for(int j = b + 1; j < 3001; ++j)
		dp[j] = 0;
}
MI res;
for(MI i : dp)
	res += i;
cout << res;