ganbarearyan45's blog

Can u point out how to improve the TC and what changes i can made to my code!
By ganbarearyan45, history, 7 months ago, In English

https://codeforces.net/problemset/problem/1831/B https://codeforces.net/contest/1831/submission/262171365 is my submission

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when there are large input or output put these 2 lines at the start of your main : ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

they will fast input output , also use '\n' or "\n" instead of endl

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

so after u do these two optimization , still TLE (time limit .... )

what u do that u take each value from a or b and count the mx subarray in a , b : so for 2*n values u iterate over a , b so your time complexity( search about it if u don't know it) is O ( n * n ) which is large enough to get TLE

but what if we preprocess the mxa[elemnt] >> max subarray that contains only elemnt , mxb[elemnt] so you won'y need the functions that takes n instruction to answer fn(a,ele) , fn(b,ele)

so know we need to think how to build mxa[ele] ... don't read this untill u try to find out how >> u can iterate over a one time with cnt = 0 : a[i]!=a[i-1] >> cnt=1 >> u start a new subarray a[i]==a[i-1] >> cnt++ mxa[a[i]] = max(mxa[a[i]] , cnt) >> u don't need to wait untill subarray is closed

https://codeforces.net/contest/1831/submission/262226998

→ Reply