USACO 2016 January Contest, Platinum Problem 1. Fort Moo

http://www.usaco.org/index.php?page=viewproblem2&cpid=600

Tip : try to O(n^4) --> O(n^3 lg n)

O (n^3 lg n)

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAX_N = 206;
const int INF = 1e9 + 7;

struct Treap {
    Treap *lc,*rc;
    int val;
    int pri;
    int key;
    int mx;
    Treap(int _key,int _val) {
        key = _key;
        mx = val = _val;
        lc=rc=NULL;
        pri=rand();
    }
};

int Mx(Treap *t) {
    return t?t->mx:-INF;
}

int Val(Treap* t) {
    return t?t->val:-INF;
}

void pull(Treap* t) {
    t->mx = max(max(Mx(t->lc),Mx(t->rc)),t->val);
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    else if (a->pri >= b->pri) {
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
//    cout<<"in1\n";
    if (!t) a=b=NULL;
    else if (t->key <= k) {
//        cout<<"in\n";
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
//        cout<<"success pull\n";
    }
    else {
//        cout<<"what\n";
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

Treap* root;

void Build(int n) {
//    cout<<"n="<<n<<endl;
    root = NULL;
    for (int i=1;n>=i;i++) {
        root = merge(root,new Treap(i,-INF));
    }
}

void modify(int pos,int val) {
//    cout<<"pos = "<<pos<<endl;
    Treap *tl,*tr;
    split(root,pos-1,tl,root);
//    cout<<"Ready\n";
    split(root,pos,root,tr);
    root->val = root->mx = val;
    root = merge(merge(tl,root),tr);
//    cout<<"root->val = "<<root->val<<endl;
}

int query1(Treap* t,int lim) {
//    cout<<"t->ley = "<<t->key<<endl;
//    cout<<"t->val = "<<t->val<<endl;
    int l=Mx(t->lc);
    int m=t->val;
    int r=Mx(t->rc);
    if (r>=lim) return query1(t->rc,lim);
    else if (m>=lim) return t->key;
    else if (l>=lim) return query1(t->lc,lim);
    return t->key;
}

int query(int L,int R,int lim) {
//    cout<<"L="<<L<<" , R="<<R<<" , lim="<<lim<<endl;
    if (L>R) return -INF;
    Treap *tl,*tr;
    split(root,L-1,tl,root);
    split(root,R,root,tr);
//    cout<<"root->mx = "<<root->mx<<endl;
    int ret=-INF;
    if (root->mx >= lim) {
        ret = query1(root,lim);
    }
    root = merge(merge(tl,root),tr);
    return ret;
}

int mp[MAX_N][MAX_N];
char c[MAX_N];
int dp1[MAX_N][MAX_N]; //down
int dp2[MAX_N][MAX_N]; //right

int main () {
    srand(time(NULL));
    if (fopen("fortmoo.in","r")) {
        freopen("fortmoo.in","r",stdin);
        freopen("fortmoo.out","w",stdout);
    }
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        getchar();
        for (int i=1;n>=i;i++) {
            scanf("%s",c);
            for (int j=1;m>=j;j++) {
                mp[i][j] = (c[j-1]=='.'?1:0);
                if(mp[i][j]==0) {
                    dp1[i][j] = dp2[i][j] = -1;
                }
            }
        }
        for (int i=n;i>=1;i--) {
            for (int j=m;j>=1;j--) {
                if (i==n && mp[i][j]==1) {
                    dp1[i][j]=0;
                }
                if (j==m && mp[i][j]==1) {
                    dp2[i][j]=0;
                }
                if (mp[i][j]==1) {
                    if (i!=n)dp1[i][j] = dp1[i+1][j]+1;
                    if (j!=m)dp2[i][j] = dp2[i][j+1]+1;
                }
            }
        }
        Build(m);
        int ans=-1;
        for (int i=1;n>=i;i++) {
            for (int j=1;m>=j;j++) {
//                cout<<"i="<<i<<" , j="<<j<<endl;
                if (mp[i][j] == -1) continue;
                if (root->val == -INF) {
                    int k=j;
                    while (k<=m && mp[i][k]==1) {
//                        cout<<"k="<<k<<", dp = "<<dp1[i][k]<<endl;
                        modify(k,dp1[i][k]);
                        k++;
//                        cout<<"k="<<k<<endl;
                    }
                }
//                cout<<"on\n";
                modify(j,-INF);
                for (int k=i;n>=k && mp[k][j]==1;k++) {
//                    cout<<"k= "<<k<<endl;
//                    cout<<"Dp 2 = "<<dp2[k][j]<<endl;
                    int ret=-INF;
                    if (j+1<=m) ret=query(j+1,j+dp2[k][j],k-i);
//                    cout<<"ret = "<<ret<<endl;
                    if (ret == -INF) {
                        ret=j;
                    }
                    ret = (ret-j+1) * (k-i+1);
                    if (ret>ans) ans=ret;
                }
            }
        }
        printf("%d\n",ans);
    }
}