HSNU Online Judge Problem : 255 - Empodia

HOJ255.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
struct Range{
    int l, r;
    Range(): l(0), r(0) {}
    Range(int ll, int rr): l(ll), r(rr) {}
    bool empty() const { return l == r; }
};
 
Range operator + (const Range& lhs, const Range& rhs){
    if(lhs.empty()) return rhs;
    if(rhs.empty()) return lhs;
    return Range(min(lhs.l, rhs.l), max(lhs.r, rhs.r));
}
 
bool operator < (const Range& lhs, const Range& rhs){
    return lhs.l < rhs.l; // enough in this program
}
 
Range empodia(int l, int r);
 
int num[1100000];
//int rev[1100000];
vector<Range> ranges;
 
int main(){
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", num + i);
//        rev[num[i]] = i;
    }
    empodia(0, m);
    sort(ranges.begin(), ranges.end());
    printf("%d\n", ranges.size());
    for(int i = 0; i < (int) ranges.size(); i++){
        printf("%d %d\n", ranges[i].l + 1, ranges[i].r);
    }
}
 
Range empodio(int l, int r, int mid);
Range empodia(int l, int r){
//    fprintf(stderr, "empodia %d %d\n", l, r);
    if(r - l < 4){
        return Range();
    } else {
        int mid = (l + r) / 2;
        Range r1 = empodia(l, mid);
        Range r2 = empodia(mid, r);
        Range r3 = empodio(r1.empty() ? l : r1.r - 1, r2.empty() ? r : r2.l + 1, mid);
        return r1 + r2 + r3;
    }
}
 
Range empodio(int l, int r, int mid) {
//    fprintf(stderr, "empodio %d %d %d\n", l, r, mid);
    int ll = mid - 1, rr = mid + 1;
    int mini = min(num[ll], num[mid]), maxi = max(num[ll], num[mid]);
    while(true){
        // satisfies condition 1
        while(num[ll] != mini || num[rr - 1] != maxi) {
            if(num[ll] != mini) {
                if(ll == l) return Range();
                ll--;
                mini = min(mini, num[ll]);
                maxi = max(maxi, num[ll]);
            } else {
                if(rr == r) return Range();
                mini = min(mini, num[rr]);
                maxi = max(maxi, num[rr]);
                rr++;
            }
        }
        if(rr - ll == maxi - mini + 1){
            ranges.push_back(Range(ll, rr));
            return Range(ll, rr);
        }
        if(maxi - mini + 1 >= r - l)
            return Range();
        // TODO pending optimization
        bool is_found = false;
        int found_i;
        for(int i = l; i < r; i++){
            if((i < ll || rr <= i) && mini <= num[i] && num[i] <= maxi){
                is_found = true;
                found_i = i;
                break;
            }
        }
        // end of pending optimization
        if(!is_found)
            return Range();
        while(found_i < ll){
            ll--;
            mini = min(mini, num[ll]);
            maxi = max(maxi, num[ll]);
        }
        while(found_i >= rr){
            mini = min(mini, num[rr]);
            maxi = max(maxi, num[rr]);
            rr++;
        }
    }
}