ilovehitagi's blog

By ilovehitagi, history, 6 weeks 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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't implemented a BIT solution, but found one that got accepted. Hopefully, it helps. submission

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it does help!! thanks a lot :D

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    kind of surprised how my solution is barely getting A/C at 1.9 seconds but the submission you linked gets A/C at 0.19 seconds. I essentially did the same thing..

    Code
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my mod_sum() was slowing down the code. I changed it to

      New Function

      This made the code faster by 1.4 seconds.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Weird, i was able to pass with n^2 log n with segtree, that afaik has a higher constant factor than Binary Indexed Tree. It must be something wrong or slowing down your bit.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh well, I'll look at my code some more, maybe I'll figure something out. Thanks man

»
6 weeks 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;