psycos.cpp

#include <iostream>
#include <vector>

using namespace std;

class Psycos {
public:
    Psycos(const vector<int> &a) : a(a) {};
    int nextPeak(int i) {
        /* return next peak on the right index or -1 if there is no more peaks */
        return -1;
    }
    int bigger(int i) {
        /* return index of next element on the right which is bigger than a[i] */
        return a.size();
    }
    int closestPeakBack(int i) {
        /*
         * let i = bigger(j)
         * return index of peak in the range [j, i), such that
         * it is bigger than all the other peaks in this range
         */
        return -1;
    }
    int countAbyss(int i, int j) {
        /* count number of steps for a[i] to fill the abyss [i, j)
         * where we assume a[i] > a[j-1]
         * divide and conquer:
         * 1. find the highest peak m, if it is outside, return the right height
         * 2. then [i, m) and [m, bigger m) are abysses and we can compute counts
         *    for them recursively
         * 3. to get the result we need to compute c([i,m)) + max(0, c([m, bigger m))) + height(bigger m, j)
         */
    }
    int count() {
        int i = 0, j = 0, cnt = 0;
        while (true) {
            i = nextPeak(j);
            if (i == -1) break;
            j = bigger(i);
            cnt += countAbyss(i, j);
            if (j == a.size()) break;
        }
        return cnt;
    }
private:
    vector<int> a;
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}