I'm unable to find any resources(with some proofs) on how to find certificate for lambda(a.k.a. Lagrange) dp optimization for non-strict convex functions. Any help is highly appreciated!

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3627 |

4 | ksun48 | 3547 |

5 | Miracle03 | 3480 |

6 | ecnerwala | 3400 |

7 | peehs_moorhsum | 3384 |

8 | maroonrk | 3361 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 209 |

2 | Um_nik | 196 |

3 | YouKn0wWho | 192 |

4 | Errichto | 182 |

5 | awoo | 181 |

6 | sus | 180 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

9 | SecondThread | 170 |

9 | Radewoosh | 170 |

You are given 4 integer arrays *A*, *P* and *B*, *Q* of size *N* and *M* queries. Initially, elements of *A* and *B* are 0, and elements of *P* and *Q* are sorted in non-decreasing order and have constraints 0 ≤ *x* ≤ 10^{9}.

There are 3 types of queries:

- 0 ≤
*x*≤ 10^{9}; 1 ≤*i*≤*N*;*A*_{i}=*x* - 0 ≤
*x*≤ 10^{9}; 1 ≤*i*≤*N*;*B*_{i}=*x* - 0 ≤
*x*≤ 10^{9}; 1 ≤*y*≤ 10^{18}; Find minimum*i*, such that

There is an easy solution with time complexity *O*(*Nlog*^{2}*N*): store *A* and *B* in BIT, when you need to answer query, binary search by *i*, and check whether condition holds true. I'm looking for solution with time complexity *O*(*NlogN*). Any ideas about that?

Hello Codeforces!

I’d like you to invite for CodeChef June Lunchtime that will start at 19:30 IST of 24-th June 2017 (check your time zone here) and will last 3 hours.

The author of problems is me, never_giveup, while Lewin is a tester and mareksom is the secondary Tester. The editorialist is pkacprzak. Translators: CherryTree (Russian), huzecong (Mandarin) and VNOI team (Vietnamese).

There is no registration required, anybody with a CodeChef handle can participate. Top **school** participants can win CodeChef laddus (details on the contest page).

You will be provided 4 problems with subtasks (IOI-style grading). Ties are broken by time of reaching your final score.

Remember about subtasks if you can't solve a problem for the full score, and read the editorial after the contest.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2021 23:35:23 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|