LA3548 Fortune at El Dorado

/*
    Problem : http://poj.org/problem?id=2899
    Problem : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=219&page=show_problem&problem=1549

    Idea from this code
    https://github.com/renzov/Red_Crown/blob/master/Live%20Archive/3548.cpp
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
#define lli long long int

struct SegmentTree
{
    vector<int> s;      // tree
    vector<int> u;      // update
    int n;

    SegmentTree( int _n );
    int get( int l , int r );
    int get(int p , int l , int r , int x , int y );
    void propagate( int p , int l , int r );
    void update( int l , int r , int d );
    void update( int p , int l , int r , int x , int y , int d );
};

int x[1005] , y[1005];
struct E
{
    int time , type , val;      // type : 0=add  , 1=delete
    E( int _ti , int _ty , int _v ) { time = _ti , type = _ty , val = _v; }
    E() {}
    bool operator < ( const E& x )  const
    {
        if ( time != x.time ) return time < x.time;
        if ( type != x.type ) return type < x.type;
        return val < x.val;
    }
} e[2005];


int main()
{
    int T; scanf( "%d" , &T );
    while ( T-- )
    {
        int n , m;
        scanf( "%d %d" , &n , &m );
        int minX = 1005 , maxX = 0;
        int minY = 1005 , maxY = 0;
        for ( int i=0 ; i<n ; i++ )
        {
            scanf( "%d %d" , &y[i] , &x[i] );
            // y[i] = i+1 , x[i] = i+1;
            minY = min( minY , y[i] );
            maxY = max( maxY , y[i] );
            minX = min( minX , x[i] );
            maxX = max( maxX , x[i] );
        }

        if ( (n == 0) || (m == 0) )
        {
            printf( "0\n" );
            continue;
        }

        int ans = 0;
        {
            int S = min( maxX-minX+1 , m );
            for ( int w=1 ; w<=S ; w++ )        // set fixed width and height and walk on columns
            {
                if ( (m/w) == (m/(w+1)) ) continue;     // simple and nice optimization !!!
                int h = m / w;

                for ( int i=0 ; i<n ; i++ )
                {
                    e[2*i] = E( x[i] , 0 , y[i] );          // time to add
                    e[2*i + 1] = E( x[i]+w , 1 , y[i] );    // time to delete
                }
                sort( e , e+2*n );

                int sz = maxY - minY + 1;
                SegmentTree st( sz + 5 );
                for ( int i=0 ; i<2*n ; i++ )
                {
                    int taim = e[i].time , type = e[i].type , val = e[i].val;

                    if ( type == 0 )        // add
                    {
                        st.update( max(1 , val-h-minY+1) , val-minY+1 , +1 );
                        ans = max( ans , st.get( 0 , sz ) );
                    }
                    else if ( type == 1 )   // delete
                    {
                        st.update( max(1 , val-h-minY+1) , val-minY+1 , -1 );
                    }
                }
            }
        }

        printf( "%d\n" , ans );
    }

    return 0;
}


// struct SegmentTree
// {
    SegmentTree::SegmentTree( int _n )
    {
        n = _n;
        s.resize(6*n+5 , 0);
        u.resize(6*n+5 , 0);
    }

    int SegmentTree::get( int l , int r )
    {
        return get( 1 , 1 , n , l , r );
    }

    int SegmentTree::get(int p , int l , int r , int x , int y )
    {
        if ( r < x || l > y ) return 0;
        propagate(p , l , r);
        if ( l>=x && r<=y ) return s[p];

        int L = p*2 , R = p*2+1 , m = (l+r)/2;
        int ansL = get( L , l , m , x , y );
        int ansR = get( R , m+1 , r , x , y );
        return max(ansL , ansR);
    }

    void SegmentTree::propagate( int p , int l , int r )
    {
        int L = p*2 , R = L+1 , S = r-l+1;
        s[p] += u[p];
        if (L < s.size()) u[L] += u[p];
        if (R < s.size()) u[R] += u[p];
        u[p] = 0;
    }

    void SegmentTree::update( int l , int r , int d )
    {
        update( 1 , 1 , n , l , r , d );
    }

    void SegmentTree::update( int p , int l , int r , int x , int y , int d )
    {
        if ( r < x || l > y ) { propagate(p , l , r); return; }
        if ( l>=x && r<=y )
        {
            u[p] += d;
            propagate(p , l , r);
            return;
        }

        propagate(p , l , r);
        int L = p*2 , R = p*2+1 , m = (l+r)/2;
        update( L , l , m , x , y , d );
        update( R , m+1 , r , x , y , d );
        s[p] = max( s[L] , s[R] );
    }
// }