BZOJ 1637 Balanced Lineup

题目大意

一堆牛站在一个数轴上。每个牛都有自己的唯一位置（数轴上）和一个种族（0/1）。求一个最长区间使得种族为0和1的牛的数量相同。

又是一道Balanced Lineup = =

这不就是低配版JOIOJI嘛= =

然而可爱的我并没有发现，光荣的写了个O(N^2)……有种噶韭菜的感觉= =

这道题直接前缀和，这里可以把0的点改成-1，这样的话就不用%了，直接值相等的就是正解了= =

然后debug出好多错误……不管了= =

#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
    int pos,val,nex;
}s[50010];
int n,ans;
bool cmpa(node tx,node ty)
{
    return tx.pos<ty.pos;
}
bool cmpb(node tx,node ty)
{
    if(tx.val==ty.val) return tx.pos<ty.pos;
    return tx.val<ty.val;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&s[i].val,&s[i].pos);
    for(int i=1;i<=n;++i) if(s[i].val==0) s[i].val=-1;
    n++,s[n].val=0,s[n].pos=0;
    sort(s+1,s+n+1,cmpa);
    for(int i=1;i<n;++i) s[i].nex=s[i+1].pos;
    s[n].nex=s[n].pos;
    for(int i=1;i<=n;++i) s[i].val=s[i-1].val+s[i].val;
    sort(s+1,s+n+1,cmpb);
    //for(int i=1;i<=n;++i) printf("%d %d %d\n",s[i].pos,s[i].nex,s[i].val);
    int tmp=0;
    s[0].val=-10000;
    for(int i=1;i<=n;++i)
        if(s[i].val!=s[i-1].val)
        {
            if(i!=1&&i!=2) ans=max(ans,s[i-1].pos-s[tmp].nex);
            //printf("%d %d %d %d %d %d\n",i,ans,s[i-1].pos,s[tmp].nex,i,tmp);
            tmp=i;
        }
    if(tmp!=n) ans=max(ans,s[n].pos-s[tmp].nex);
    printf("%d",ans);
    return 0;
}