#include<iostream>
#include<stdio.h>
using namespace std ;
#define MAXN 300007
#define inf 1000000007
int n , q ;
class Tree {
public :
int tr[ 3 * MAXN ] ;
bool fl[ 3 * MAXN ] ;
void init ( int where , int IL , int IR ) {
tr[ where ] = IL ;
fl[ where ] = false ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
void update ( int where , int IL , int IR , int CURL , int CURR , int val ) {
if ( CURL > CURR ) { return ; }
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
tr[ where ] = min ( tr[ where ] , val ) ;
fl[ where ] = true ;
return ;
}
int mid = ( IL + IR ) / 2 ;
update ( 2 * where , IL , mid , CURL , CURR , val ) ;
update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
}
int query ( int where , int IL , int IR , int pos ) {
if ( pos < IL || IR < pos ) { return ( 2 * inf ) ; }
if ( IL == IR ) {
return ( pos - tr[ where ] ) ;
}
int ret = 0 ;
if ( fl[ where ] == true ) {
ret = max ( ret , pos - tr[ where ] ) ;
}
int mid = ( IL + IR ) / 2 ;
if ( pos <= mid ) {
ret = max ( ret , query ( 2 * where , IL , mid , pos ) ) ;
}
else {
ret = max ( ret , query ( 2 * where + 1 , mid + 1 , IR , pos ) ) ;
}
return ret ;
}
};
Tree w ;
void input ( ) {
scanf ( "%d%d" , &n , &q ) ;
w.init ( 1 , 1 , n ) ;
int i ;
for ( i = 1 ; i <= q ; i ++ ) {
int l , r , x ;
scanf ( "%d%d%d" , &l , &r , &x ) ;
int pos = l - x ;
w.update ( 1 , 1 , n , l , r , pos ) ;
}
}
void solve ( ) {
int i ;
for ( i = 1 ; i <= n ; i ++ ) {
int ret = w.query ( 1 , 1 , n , i ) ;
printf ( "%d" , ret ) ;
if ( i == n ) { printf ( "\n" ) ; }
else { printf ( " " ) ; }
}
}
int main ( ) {
input ( ) ;
solve ( ) ;
return 0 ;
}
Compilation message
trading.cpp: In function 'void input()':
trading.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d%d" , &n , &q ) ;
^
trading.cpp:61:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d%d%d" , &l , &r , &x ) ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6420 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6420 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6420 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6420 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6420 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6420 KB |
Output is correct |
| 7 |
Correct |
166 ms |
6420 KB |
Output is correct |
| 8 |
Correct |
179 ms |
6420 KB |
Output is correct |
| 9 |
Correct |
199 ms |
6420 KB |
Output is correct |
| 10 |
Correct |
176 ms |
6420 KB |
Output is correct |
| 11 |
Correct |
223 ms |
6420 KB |
Output is correct |
| 12 |
Correct |
249 ms |
6420 KB |
Output is correct |
| 13 |
Correct |
239 ms |
6420 KB |
Output is correct |
| 14 |
Correct |
229 ms |
6420 KB |
Output is correct |
| 15 |
Correct |
309 ms |
6420 KB |
Output is correct |
| 16 |
Correct |
276 ms |
6420 KB |
Output is correct |
| 17 |
Runtime error |
0 ms |
6420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Halted |
0 ms |
0 KB |
- |
