USACO 2015 December Contest, Platinum Problem 2. High Card Low Card (Platinum)

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

Key : http://codeforces.com/contest/380/problem/C

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

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
#define F first
#define S second
#define MP make_pair
const int MAX_N = 1e5 + 6;

piii operator+(const piii &p1,const piii &p2) {
    int tmp=min(p1.second.S,p2.second.F );
    return MP(p1.first+p2.first+tmp,MP(p1.second.F + p2.second.F - tmp,p1.second.S + p2.second.S - tmp));
}

int v[MAX_N]; 
vector<int> r1,r2;

struct Node {
    Node *lc,*rc;
    piii val;
    piii val2;
    Node() {
        lc=rc=NULL;
        val2=val=MP(0,MP(0,0));
    }
    void pull() {
        val = lc->val + rc->val;
        val2= lc->val2+rc->val2;
    }
};

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        if (v[L]) node->val=MP(0,MP(0,1));
        else node->val=MP(0,MP(1,0));
        return node;
    }
    int mid=(L+R)>>1;
    node->lc = Build(L,mid);
    node->rc = Build(mid+1,R);
    node->pull();
    return node;
}

void modify(Node* node,int L,int R,int pos,int val ) {
    if (L==R) {
        v[L]=val;
        if (v[L]) node->val2=MP(0,MP(0,1));
        else node->val2=MP(0,MP(1,0));
        node->val = MP(0,MP(0,0));
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
    return;
}

int main () {
    if (fopen("cardgame.in","r")) {
        freopen("cardgame.in","r",stdin);
        freopen("cardgame.out","w",stdout);
    }
    int n;
    while (scanf("%d",&n) != EOF) {
        r1.clear();
        r2.clear();
        memset(v,0,sizeof(v));
        for (int x=0;n>x;x++) {
            int i;
            scanf("%d",&i);
            v[i]=1;
            r1.push_back(i);
        }
        n*=2;
        for (int x=1;n>=x;x++) {
            if (v[x] == 0) {
                r2.push_back(x);
            }
        }
        Node* root = Build(1,n);
        int ans=root->val.first;
        int len=n/2;
//        cout<<"ans="<<ans<<endl;
        for (int x=len-1,y=0;x>=0;x--,y++) {
//            cout<<"x="<<x<<" ";
//            cout<<"r1 = "<<r1[x]<<" , r2="<<r2[y];
            modify(root,1,n,r1[x],0);
            modify(root,1,n,r2[y],1);
            ans = max(ans,root->val.first + root->val2.first);
//            cout<<" ans = "<<ans<<endl;
        }
        printf("%d\n",ans);
    }
}