struct line
{
long long a,b;
} it[ 4000010 ] ;
long long get( line a,long long x)
{
return a.a * x+ a.b ;
}
// update line x to out set
void update( long long p,long long l,long long r,line x)
{
if ( ! al[ p] ) q.push ( p) ,al[ p] = 1 ;
line y= it[ p] ;
if ( get( y,l) >= get( x,l) and get( y,r) >= get( x,r) )
return ;
if ( get( y,l) <= get( x,l) and get( y,r) <= get( x,r) )
{
it[ p] = x;
return ;
}
long long m= ( l+ r) / 2 ;
if ( get( y,l) >= get( x,l) and get( y,m) >= get( x,m) )
{
update( p* 2 + 1 ,( l+ r) / 2 + 1 ,r,x) ;
return ;
}
if ( get( y,l) <= get( x,l) and get( y,m) <= get( x,m) )
{
it[ p] = x;
update( p* 2 + 1 ,( l+ r) / 2 + 1 ,r,y) ;
return ;
}
if ( get( y,r) >= get( x,r) and get( y,m+ 1 ) >= get( x,m+ 1 ) )
{
update( p* 2 ,l,( l+ r) / 2 ,x) ;
return ;
}
if ( get( y,r) <= get( x,r) and get( y,m+ 1 ) <= get( x,m+ 1 ) )
{
it[ p] = x;
update( p* 2 ,l,( l+ r) / 2 ,y) ;
return ;
}
}
// get maximum value of at coordinate a
long long get_val( long long p,long long l,long long r,long long a)
{
if ( r< a or l> a) return - 1e18 ;
long long x= get( it[ p] ,a) ;
if ( l== r) return x;
x= max( x,get_val( p* 2 ,l,( l+ r) / 2 ,a) ) ;
x= max( x,get_val( p* 2 + 1 ,( l+ r) / 2 + 1 ,r,a) ) ;
return x;
}
c3RydWN0IGxpbmUKewoJbG9uZyBsb25nIGEsYjsKfWl0WzQwMDAwMTBdOwoKbG9uZyBsb25nIGdldChsaW5lIGEsbG9uZyBsb25nIHgpCnsKCXJldHVybiBhLmEqeCthLmI7Cn0KCgovLyB1cGRhdGUgbGluZSB4IHRvIG91dCBzZXQKdm9pZCB1cGRhdGUobG9uZyBsb25nIHAsbG9uZyBsb25nIGwsbG9uZyBsb25nIHIsbGluZSB4KQp7CglpZiAoIWFsW3BdKSBxLnB1c2gocCksYWxbcF09MTsKCWxpbmUgeT1pdFtwXTsKCWlmIChnZXQoeSxsKT49Z2V0KHgsbCkgYW5kIGdldCh5LHIpPj1nZXQoeCxyKSkgCgkJcmV0dXJuOwoJaWYgKGdldCh5LGwpPD1nZXQoeCxsKSBhbmQgZ2V0KHkscik8PWdldCh4LHIpKQoJewoJCWl0W3BdPXg7CgkJcmV0dXJuOwoJfQoJbG9uZyBsb25nIG09KGwrcikvMjsKCWlmIChnZXQoeSxsKT49Z2V0KHgsbCkgYW5kIGdldCh5LG0pPj1nZXQoeCxtKSkKCXsKCQl1cGRhdGUocCoyKzEsKGwrcikvMisxLHIseCk7CgkJcmV0dXJuOwoJfQoJaWYgKGdldCh5LGwpPD1nZXQoeCxsKSBhbmQgZ2V0KHksbSk8PWdldCh4LG0pKQoJewoJCWl0W3BdPXg7CgkJdXBkYXRlKHAqMisxLChsK3IpLzIrMSxyLHkpOwoJCXJldHVybjsKCX0KCWlmIChnZXQoeSxyKT49Z2V0KHgscikgYW5kIGdldCh5LG0rMSk+PWdldCh4LG0rMSkpCgl7CgkJdXBkYXRlKHAqMixsLChsK3IpLzIseCk7CgkJcmV0dXJuOwoJfQoJaWYgKGdldCh5LHIpPD1nZXQoeCxyKSBhbmQgZ2V0KHksbSsxKTw9Z2V0KHgsbSsxKSkKCXsKCQlpdFtwXT14OwoJCXVwZGF0ZShwKjIsbCwobCtyKS8yLHkpOwoJCXJldHVybjsKCX0KfQoKCi8vIGdldCBtYXhpbXVtIHZhbHVlIG9mIGF0IGNvb3JkaW5hdGUgYQpsb25nIGxvbmcgZ2V0X3ZhbChsb25nIGxvbmcgcCxsb25nIGxvbmcgbCxsb25nIGxvbmcgcixsb25nIGxvbmcgYSkKewoJaWYgKHI8YSBvciBsPmEpIHJldHVybiAtMWUxODsKCWxvbmcgbG9uZyB4PWdldChpdFtwXSxhKTsKCWlmIChsPT1yKSByZXR1cm4geDsKCXg9bWF4KHgsZ2V0X3ZhbChwKjIsbCwobCtyKS8yLGEpKTsKCXg9bWF4KHgsZ2V0X3ZhbChwKjIrMSwobCtyKS8yKzEscixhKSk7CglyZXR1cm4geDsKfQ==
compilation info
prog.cpp: In function ‘void update(long long int, long long int, long long int, line)’:
prog.cpp:15:7: error: ‘al’ was not declared in this scope
if (!al[p]) q.push(p),al[p]=1;
^~
prog.cpp:15:14: error: ‘q’ was not declared in this scope
if (!al[p]) q.push(p),al[p]=1;
^
prog.cpp: In function ‘long long int get_val(long long int, long long int, long long int, long long int)’:
prog.cpp:56:34: error: ‘max’ was not declared in this scope
x=max(x,get_val(p*2,l,(l+r)/2,a));
^
stdout