好文收藏夹

【 CF739C 】 Alyona and towers time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Alyona has built  n  towers by putting small cubes some on the top of others. Each cube has size  1 × 1 × 1 . A tower is a non-zero amount of cubes standing on the top of each other. The towers are next to each other, forming a row. Sometimes Alyona chooses some segment towers, and put on the top of each tower several cubes. Formally, Alyona chooses some segment of towers from  l i  to  r i  and adds  d i  cubes on the top of them. Let the sequence  a 1 ,  a 2 , ...,  a n  be the heights of the towers from left to right. Let's call as a segment of towers  a l ,  a l  + 1 , ...,  a r  a hill if the following condition holds: there is integer  k  ( l  ≤  k  ≤  r ) such that  a l  <  a l  + 1  <  a l  + 2  < ... <  a k  >  a k  + 1  ...