#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 200007 ;
const int inf = 1000000007 ;
int n , m ;
int h[ MAXN ] , a[ MAXN ] , b[ MAXN ] ;
pair < int , int > qlist[ MAXN ] ;
int ans[ MAXN ] ;
vector < pair < int , int > > v[ MAXN ] ;
vector < int > to_solve[ MAXN ] ;
class Tree {
public :
int tr[ 4 * MAXN ] , ret[ 4 * MAXN ] ;
int lazy[ 4 * MAXN ] ;
void push_lazy ( int where , int IL , int IR ) {
ret[ where ] = max ( ret[ where ] , tr[ where ] + lazy[ where ] ) ;
if ( IL != IR ) {
lazy[ 2 * where ] = max ( lazy[ 2 * where ] , lazy[ where ] ) ;
lazy[ 2 * where + 1 ] = max ( lazy[ 2 * where + 1 ] , lazy[ where ] ) ;
}
lazy[ where ] = -inf ;
}
void init ( int where , int IL , int IR ) {
tr[ where ] = lazy[ where ] = ret[ where ] = -inf ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
void upd_pos ( int where , int IL , int IR , int pos , int nw ) {
push_lazy ( where , IL , IR ) ;
if ( IR < pos || pos < IL ) { return ; }
if ( IL == IR ) {
tr[ where ] = nw ;
return ;
}
int mid = ( IL + IR ) / 2 ;
upd_pos ( 2 * where , IL , mid , pos , nw ) ;
upd_pos ( 2 * where + 1 , mid + 1 , IR , pos , nw ) ;
tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
ret[ where ] = max ( ret[ 2 * where ] , ret[ 2 * where + 1 ] ) ;
}
void upd_range ( int where , int IL , int IR , int CURL , int CURR , int val ) {
push_lazy ( where , IL , IR ) ;
if ( IL > IR || CURL > CURR ) { return ; }
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
lazy[ where ] = val ;
push_lazy ( where , IL , IR ) ;
return ;
}
int mid = ( IL + IR ) / 2 ;
upd_range ( 2 * where , IL , mid , CURL , CURR , val ) ;
upd_range ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
ret[ where ] = max ( ret[ 2 * where ] , ret[ 2 * where + 1 ] ) ;
}
int query ( int where , int IL , int IR , int CURL , int CURR ) {
push_lazy ( where , IL , IR ) ;
if ( IL > IR || CURL > IR ) { return -inf ; }
if ( IR < CURL || CURR < IL ) { return -inf ; }
if ( CURL <= IL && IR <= CURR ) { return ret[ where ] ; }
int mid = ( IL + IR ) / 2 ;
return max ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
}
};
Tree w ;
void input ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> h[ i ] >> a[ i ] >> b[ i ] ;
}
cin >> m ;
for ( int i = 1 ; i <= m ; ++ i ) {
cin >> qlist[ i ].first >> qlist[ i ].second ;
ans[ i ] = -inf ;
}
}
void solve ( ) {
for ( int iter = 0 ; iter < 2 ; ++ iter ) {
w.init ( 1 , 1 , n ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
int st = i + a[ i ] , en = i + b[ i ] + 1 ;
if ( st <= n ) {
v[ st ].push_back ( { i , 1 } ) ;
}
if ( en <= n ) {
v[ en ].push_back ( { i , -1 } ) ;
}
}
for ( int i = 1 ; i <= m ; ++ i ) {
to_solve[ qlist[ i ].second ].push_back ( i ) ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
for ( auto e : v[ i ] ) {
int id = e.first , type = e.second ;
if ( type == 1 ) {
w.upd_pos ( 1 , 1 , n , id , -h[ id ] ) ;
}
else {
w.upd_pos ( 1 , 1 , n , id , -inf ) ;
}
}
int st = i - b[ i ] ;
int en = i - a[ i ] ;
if ( st < 1 ) { st = 1 ; }
if ( en < st ) { en = st ; }
w.upd_range ( 1 , 1 , n , st , en , h[ i ] ) ;
for ( auto id : to_solve[ i ] ) {
ans[ id ] = max ( ans[ id ] , w.query ( 1 , 1 , n , qlist[ id ].first , i ) ) ;
}
}
for ( int i = 1 ; i < n - i + 1 ; ++ i ) {
swap ( h[ i ] , h[ n - i + 1 ] ) ;
swap ( a[ i ] , a[ n - i + 1 ] ) ;
swap ( b[ i ] , b[ n - i + 1 ] ) ;
}
for ( int i = 1 ; i <= m ; ++ i ) {
int x = qlist[ i ].first , y = qlist[ i ].second ;
qlist[ i ] = { n - y + 1 , n - x + 1 } ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
v[ i ].clear ( ) ;
to_solve[ i ].clear ( ) ;
}
}
for ( int i = 1 ; i <= m ; ++ i ) {
if ( ans[ i ] < 0 ) { ans[ i ] = -1 ; }
cout << ans[ i ] << "\n" ;
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ;
/// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
317 ms |
22056 KB |
Output is correct |
| 2 |
Correct |
347 ms |
22840 KB |
Output is correct |
| 3 |
Correct |
242 ms |
20740 KB |
Output is correct |
| 4 |
Correct |
358 ms |
22732 KB |
Output is correct |
| 5 |
Correct |
144 ms |
15948 KB |
Output is correct |
| 6 |
Correct |
356 ms |
23032 KB |
Output is correct |
| 7 |
Correct |
295 ms |
21808 KB |
Output is correct |
| 8 |
Correct |
364 ms |
22900 KB |
Output is correct |
| 9 |
Correct |
48 ms |
11632 KB |
Output is correct |
| 10 |
Correct |
356 ms |
22844 KB |
Output is correct |
| 11 |
Correct |
248 ms |
17276 KB |
Output is correct |
| 12 |
Correct |
361 ms |
22780 KB |
Output is correct |
| 13 |
Correct |
273 ms |
22964 KB |
Output is correct |
| 14 |
Correct |
255 ms |
22816 KB |
Output is correct |
| 15 |
Correct |
256 ms |
21956 KB |
Output is correct |
| 16 |
Correct |
252 ms |
21904 KB |
Output is correct |
| 17 |
Correct |
270 ms |
23468 KB |
Output is correct |
| 18 |
Correct |
266 ms |
22348 KB |
Output is correct |
| 19 |
Correct |
268 ms |
22560 KB |
Output is correct |
| 20 |
Correct |
260 ms |
22692 KB |
Output is correct |
| 21 |
Correct |
247 ms |
22660 KB |
Output is correct |
| 22 |
Correct |
266 ms |
22544 KB |
Output is correct |
| 23 |
Correct |
263 ms |
22724 KB |
Output is correct |
| 24 |
Correct |
243 ms |
21444 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
