My Code link:https://codeforces.com/contest/1678/submission/156355337
My Logic: Store all Pairs [Ai,Aj] where Ai>Aj in a 2D Vector and similarly do for Ai<Aj. Now Make 4 length arrays using these two arrays as they have required Pa < Pc and Pb>Pd pairs. If they meet the given condition check if position of elements of subsequence in original array is sorted or not using map, if sorted increment the answer.
Problem: It TLE's.
Thinking: I tired to think of optimization but unable to come up with. So can anyone help?
Your code runs in O(n^4). The size of each of the two arrays you create is O(n^2), and you iterate through all pairs.
A computer can do roughly 10^8 operations per second, but you're asking it to do roughly 5000^4, which is about 10^14, so this would take about a million seconds to finish on the largest allowed input.
You can read the solution in the editorial here.
https://codeforces.com/contest/1678/submission/156346740 I think above solution is o(n2logn) can u help me why its TLE?
[Deleted] I was wrong!
The constraints are actually made to prevent n^2 * log(n) solutions from passing. I believe the author didn't expect some of the submissions to make it through or rather at least the ones with high constant factor and therefore made a quick edit before releasing the final editorial. (It's just a possibility don't take it for real)
at n = 5000 attempting a n^2 * log sol is pretty risky, therefore you make use of really well optimized code for a data structure (like iterative segment trees and I/O optimizations which some people do, or a Fenwick which is more lightweight, etc.)
or just be cautious and don't go for the log(n) solution :) that's what struck me initially too (so I spent some time thinking and considered holding back on it till I ran out of time)