CSES - Listan halkaisu Annettuna on lista kokonaislukuja, ja tehtäväsi on laskea, monellako tavalla voit halkaista listan kahteen osaan niin, että jokainen vasemman osan alkio on pienempi kuin jokainen oikean osan alkio.

Esimerkiksi listassa $[2,1,2,5,7,6,9]$ tapoja on $3$:
  • $[2,1,2]$ ja $[5,7,6,9]$
  • $[2,1,2,5]$ ja $[7,6,9]$
  • $[2,1,2,5,7,6]$ ja $[9]$
Voit olettaa, että jokainen luku on välillä $1 \dots 10^9$ ja listalla on enintään $10^5$ lukua. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$.

Python

Toteuta tiedostoon splitlist.py funktio count, joka antaa tapojen määrän.
def count(t):
    # TODO

if __name__ == "__main__":
    print(count([1,2,3,4,5])) # 4
    print(count([5,4,3,2,1])) # 0
    print(count([2,1,2,5,7,6,9])) # 3
    print(count([1,2,3,1])) # 0
Java

Toteuta tiedostoon SplitList.java metodi count, joka antaa tapojen määrän.
public class SplitList {
    public int count(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        SplitList s = new SplitList();
        System.out.println(s.count(new int[] {1,2,3,4,5})); // 4
        System.out.println(s.count(new int[] {5,4,3,2,1})); // 0
        System.out.println(s.count(new int[] {2,1,2,5,7,6,9})); // 3
        System.out.println(s.count(new int[] {1,2,3,1})); // 0
    }
}