#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define pb push_back
#define fi first
#define se second
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
#define EXP 1e-6
#define flush mobshigeo
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
const int mod = 1e9+7 ;
const int LOG = 19 ;
const int INF = 1e9 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
typedef pair<ll,ll> pll ;
typedef vector<ll> vl ;
void add ( int &a , int b )
{
a += b ;
if ( a < 0 ) a += mod ;
if ( a >= mod ) a -= mod ;
}
template < typename T > void chkmin ( T&a , T b ) { if ( a > b ) a = b ; } ;
template < typename T > void chkmax ( T&a , T b ) { if ( a < b ) a = b ; } ;
void rf ()
{
freopen ("anten.inp","r",stdin) ;
freopen ("anten.out","w",stdout) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow (a,n/2) ;
if ( n % 2 ) return (1ll*res*res%mod*a%mod) ;
else return (1ll*res*res%mod) ;
}
int n , nq ;
struct shape {
int l , r , h ;
} a [maxn] ;
struct ape {
int ans , h ;
}T[maxn*4];
int lazy [maxn*4] ;
void down ( int id )
{
int &t = lazy [id] ;
chkmax (T[left].ans,t-T[left].h) ;
chkmax (T[right].ans,t-T[right].h) ;
chkmax (lazy[left],t) ;
chkmax (lazy[right],t) ;
t = 0 ;
}
ape combine ( ape u , ape v )
{
return {max(u.ans,v.ans),min(u.h,v.h)} ;
}
void update ( int id , int l , int r , int u , int v , int h , int op )
{
if ( l > v || r < u ) return ;
if ( u <= l && r <= v )
{
if ( op == 1 )
{
if ( h == 1 ) T [id].h = a[l].h ;
else T [id].h = INF ;
}
else
{
chkmax (T[id].ans,h-T[id].h) ;
chkmax (lazy[id],h) ;
}
return ;
}
int mid = (l+r)/2 ;
down (id) ;
update (left,l,mid,u,v,h,op) ;
update (right,mid+1,r,u,v,h,op) ;
T [id] = combine (T[left],T[right]) ;
}
int get ( int id , int l , int r , int u , int v )
{
if ( l > v || r < u ) return - 1 ;
if ( u <= l && r <= v ) return T [id].ans ;
int mid = (l+r)/2 ;
down (id) ;
return max (get(left,l,mid,u,v),get(right,mid+1,r,u,v)) ;
}
vii event [maxn] , query [maxn] ;
int ans [maxn] ;
void reset ()
{
for ( int i = 0 ; i <= n*4 ; i ++ ) T [i] = {-1,INF} , lazy [i] = 0 ;
for ( int i = 1 ; i <= n ; i ++ ) event [i].clear () ;
}
void solve ()
{
reset () ;
for ( int i = 1 ; i <= n ; i ++ )
{
int l = a [i].l , r = a [i].r , h = a[i].h ;
for ( auto x : event [i] ) update (1,1,n,x.fi,x.fi,x.se,1) ;
int L = max (i-r,1) , R = i-l ;
if ( L <= R ) update (1,1,n,L,R,h,2) ;
for ( auto x : query [i] ) chkmax (ans[x.se],get(1,1,n,x.fi,i) ) ;
if ( i + l <= n ) event [i+l].pb({i,1}) ;
if ( i + r + 1 <= n ) event [i+r+1].pb({i,-1}) ;
}
}
int main ()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0);cout.tie(0) ;
cin >> n >> nq ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i].h >> a [i].l >> a [i].r ;
for ( int i = 1 ; i <= nq ; i ++ )
{
int l , r ; cin >> l >> r ;
query [r] . pb ({l,i}) ;
}
memset ( ans , - 1 , sizeof ans ) ;
solve () ;
for ( int i = 1 ; i <= n ; i ++ ) a [i].h = INF - a [i].h ;
solve () ;
for ( int i = 1 ; i <= nq ; i ++ ) cout << ans [i] << "\n" ;
}
// std=c++11 thunopro
Compilation message
antennas.cpp: In function 'void rf()':
antennas.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen ("anten.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:43:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | freopen ("anten.out","w",stdout) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
47556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
47556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
168 ms |
90536 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
47556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
