#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 200007 ;
const int inf = 2000000007 ;
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 ] , cand[ 4 * MAXN ] ;
int lazy[ 4 * MAXN ] ;
void push_lazy ( int where , int IL , int IR ) {
cand[ where ] = max ( cand[ 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 ] = 0 ;
}
void init ( int where , int IL , int IR ) {
cand[ where ] = tr[ where ] = -inf ;
lazy[ where ] = 0 ;
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 ] ) ;
cand[ where ] = max ( cand[ 2 * where ] , cand[ 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 ) ;
cand[ where ] = max ( cand[ 2 * where ] , cand[ 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 cand[ 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 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
319 ms |
22780 KB |
Output is correct |
| 2 |
Correct |
362 ms |
23288 KB |
Output is correct |
| 3 |
Correct |
230 ms |
21296 KB |
Output is correct |
| 4 |
Correct |
368 ms |
23352 KB |
Output is correct |
| 5 |
Correct |
139 ms |
16660 KB |
Output is correct |
| 6 |
Correct |
357 ms |
23328 KB |
Output is correct |
| 7 |
Correct |
302 ms |
22416 KB |
Output is correct |
| 8 |
Correct |
347 ms |
23344 KB |
Output is correct |
| 9 |
Correct |
46 ms |
12052 KB |
Output is correct |
| 10 |
Correct |
344 ms |
23244 KB |
Output is correct |
| 11 |
Correct |
222 ms |
17776 KB |
Output is correct |
| 12 |
Correct |
361 ms |
23376 KB |
Output is correct |
| 13 |
Correct |
271 ms |
23596 KB |
Output is correct |
| 14 |
Correct |
253 ms |
23296 KB |
Output is correct |
| 15 |
Correct |
260 ms |
22380 KB |
Output is correct |
| 16 |
Correct |
241 ms |
22396 KB |
Output is correct |
| 17 |
Correct |
276 ms |
24096 KB |
Output is correct |
| 18 |
Correct |
260 ms |
22812 KB |
Output is correct |
| 19 |
Correct |
268 ms |
23200 KB |
Output is correct |
| 20 |
Correct |
262 ms |
23200 KB |
Output is correct |
| 21 |
Correct |
244 ms |
23152 KB |
Output is correct |
| 22 |
Correct |
258 ms |
23104 KB |
Output is correct |
| 23 |
Correct |
258 ms |
23320 KB |
Output is correct |
| 24 |
Correct |
250 ms |
21780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
