USACO 2014 US Open, Silver Problem 1. Fair Photography

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

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e5 + 6;
const int INF = 1e9 + 7;

pii a[MAX_N];
int pre[MAX_N];
int mx[2*MAX_N];

int main () {
    if (fopen("fairphoto.in","r")) {
        freopen("fairphoto.in","r",stdin);
        freopen("fairphoto.out","w",stdout);
    }
    int n;
    while (scanf("%d",&n) != EOF) {
        memset(pre,0,sizeof(pre));
        fill(mx,mx+2*MAX_N,-INF);
        for (int x=1;n>=x;x++) {
            int i;
            char c;
            scanf("%d %c",&i,&c);
            a[x] = make_pair(i,c=='W'?1:-1);
        }
        sort(a+1,a+n+1);
        for (int x=1;n>=x;x++) {
            pre[x] = pre[x-1] + a[x].second;
            mx[pre[x]+MAX_N] = x;
        }
        for (int x=2*MAX_N-2;x>=0;x--) {
            mx[x] = max(mx[x],mx[x+1]);
        }
        int ans=-INF;
        for (int x=1;n>=x;x++) {
            int s = -a[x].second + pre[x];
            if (x==1) s=-a[x].second;
            s += MAX_N;
            int t=mx[s];
//            cout<<"x = "<<x<<" , s= "<<s<<" , t ="<<t<<endl;
            if (t==-INF) continue;
            if ((t-x)%2==0) t--;
            ans = max(ans,a[t].first-a[x].first);
        }
        printf("%d\n",ans);
    }
}