Ssaranshh13's blog

By Ssaranshh13, history, 23 months ago, In English

Link to the problem : CSES- Subset Queries In the problem, I flattened the tree and used Euler tours to access subtrees, and used a segment tree to answer the queries on the subtrees. The solution's overall time complexity should be O(nlogn). But it's giving TLE on a larger value of n.

My submission: Click here

Please tell me where I am doing this wrong. Thank you in advance.

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By Ssaranshh13, history, 2 years ago, In English

I have written the code to solve 1609C - Complex Market Analysis problem, but it gives TLE. I think the complexity of my soln. is O(n*log(log(n) because of Seive rest of the work i have done in linear time. My approach is as follows:

Suppose arr[i] is prime I have calculated the number of chains of 1 on left of arr[i] and similarly on right of arr[i]. Then i have used sum+=onesLeft[i]+onesRight[i]+onesLeft[i]*onesRight[i]; to get the answer.

Here is my submission ----> https://codeforces.net/contest/1609/submission/160055418. Please tell where I am wrong in calculating the time complexity? Thanks in advance.

Full text and comments »

Tags dp
  • Vote: I like it
  • -10
  • Vote: I do not like it