Блог пользователя ilovehitagi

Автор ilovehitagi, история, 3 года назад, По-английски

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
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;