Poj Solution 2892

http://poj.org/problem?id=2892

#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>

using namespace std;

map< int, int, less<int> > s;

int query( int k ) {
    map<int, int, less<int> >::iterator it;
    it = s.lower_bound( k );
    if( it->second > k )
        return 0;
    return it->first - it->second + 1;
}

void destroy( int k ) {
    map< int, int, less<int> >::iterator it;
    it = s.lower_bound( k );
    
    if( it->second > k )
        return;

    pair<int,int> p = *it;
    s.erase( it );
    
    
    if( p.second <= k-1 )
        s.insert( pair<int,int>( k-1, p.second ) );
    if( p.first >= k+1 )
        s.insert( pair<int,int>( p.first, k+1 ) );
}

void rebuild( int k ) {
    map< int, int, less<int> >::iterator it1, it2;
    it1 = s.lower_bound( k+1 );
    it2 = s.lower_bound( k-1 );
    
    pair<int,int> p;
    
    if( it1->second == k+1 ) {
        p.first = it1->first;
        s.erase( it1 );
    }
    else
        p.first = k;
    
    if( it2->first == k-1 ) {
        p.second = it2->second;
        s.erase( it2 );
    }
    else
        p.second = k;
    s.insert( p );
}


stack<int> sk;

int main( ) {
    int n, m, k;
    char c[2];
    scanf( "%d%d", &n, &m );
    s.insert( pair<int,int>( n, 1 ) );
    while( m-- ) {
        scanf( "%1s", c );
        if( c[0] == 'D' ) {
            scanf( "%d", &k );
            sk.push( k );
            destroy( k );
        }
        else if( c[0] == 'Q' ) {
            scanf( "%d", &k );
            printf( "%dn", query( k ) );
        }
        else {
            rebuild( sk.top() );
            sk.pop();
        }
            
    }
    return 0;
}