#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 ("bai1.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) ;
// rf () ;
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i].h >> a [i].l >> a [i].r ;
cin >> nq ;
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 ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
15016 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14828 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14936 KB |
Output is correct |
15 |
Correct |
3 ms |
14936 KB |
Output is correct |
16 |
Correct |
3 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
15012 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14764 KB |
Output is correct |
24 |
Correct |
3 ms |
14936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
15016 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14828 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14936 KB |
Output is correct |
15 |
Correct |
3 ms |
14936 KB |
Output is correct |
16 |
Correct |
3 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
15012 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14764 KB |
Output is correct |
24 |
Correct |
3 ms |
14936 KB |
Output is correct |
25 |
Correct |
86 ms |
19028 KB |
Output is correct |
26 |
Correct |
14 ms |
15452 KB |
Output is correct |
27 |
Correct |
119 ms |
20820 KB |
Output is correct |
28 |
Correct |
121 ms |
21076 KB |
Output is correct |
29 |
Correct |
85 ms |
19020 KB |
Output is correct |
30 |
Correct |
82 ms |
19028 KB |
Output is correct |
31 |
Correct |
86 ms |
20048 KB |
Output is correct |
32 |
Correct |
123 ms |
21072 KB |
Output is correct |
33 |
Correct |
107 ms |
20560 KB |
Output is correct |
34 |
Correct |
61 ms |
17748 KB |
Output is correct |
35 |
Correct |
115 ms |
20816 KB |
Output is correct |
36 |
Correct |
120 ms |
20880 KB |
Output is correct |
37 |
Correct |
69 ms |
17744 KB |
Output is correct |
38 |
Correct |
117 ms |
20096 KB |
Output is correct |
39 |
Correct |
20 ms |
15700 KB |
Output is correct |
40 |
Correct |
116 ms |
20052 KB |
Output is correct |
41 |
Correct |
89 ms |
18880 KB |
Output is correct |
42 |
Correct |
114 ms |
19984 KB |
Output is correct |
43 |
Correct |
41 ms |
16464 KB |
Output is correct |
44 |
Correct |
115 ms |
20108 KB |
Output is correct |
45 |
Correct |
24 ms |
15704 KB |
Output is correct |
46 |
Correct |
116 ms |
20112 KB |
Output is correct |
47 |
Correct |
32 ms |
16208 KB |
Output is correct |
48 |
Correct |
122 ms |
20044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
24912 KB |
Output is correct |
2 |
Correct |
285 ms |
30288 KB |
Output is correct |
3 |
Correct |
177 ms |
27008 KB |
Output is correct |
4 |
Correct |
271 ms |
30032 KB |
Output is correct |
5 |
Correct |
112 ms |
22348 KB |
Output is correct |
6 |
Correct |
271 ms |
30036 KB |
Output is correct |
7 |
Correct |
228 ms |
28692 KB |
Output is correct |
8 |
Correct |
282 ms |
30304 KB |
Output is correct |
9 |
Correct |
37 ms |
18008 KB |
Output is correct |
10 |
Correct |
269 ms |
30044 KB |
Output is correct |
11 |
Correct |
167 ms |
26352 KB |
Output is correct |
12 |
Correct |
275 ms |
30028 KB |
Output is correct |
13 |
Correct |
183 ms |
28480 KB |
Output is correct |
14 |
Correct |
175 ms |
28552 KB |
Output is correct |
15 |
Correct |
169 ms |
28680 KB |
Output is correct |
16 |
Correct |
150 ms |
29088 KB |
Output is correct |
17 |
Correct |
194 ms |
28876 KB |
Output is correct |
18 |
Correct |
167 ms |
29096 KB |
Output is correct |
19 |
Correct |
177 ms |
28532 KB |
Output is correct |
20 |
Correct |
171 ms |
28484 KB |
Output is correct |
21 |
Correct |
157 ms |
28104 KB |
Output is correct |
22 |
Correct |
170 ms |
28456 KB |
Output is correct |
23 |
Correct |
171 ms |
28364 KB |
Output is correct |
24 |
Correct |
149 ms |
28724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
15016 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14828 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14936 KB |
Output is correct |
15 |
Correct |
3 ms |
14936 KB |
Output is correct |
16 |
Correct |
3 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
15012 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14764 KB |
Output is correct |
24 |
Correct |
3 ms |
14936 KB |
Output is correct |
25 |
Correct |
86 ms |
19028 KB |
Output is correct |
26 |
Correct |
14 ms |
15452 KB |
Output is correct |
27 |
Correct |
119 ms |
20820 KB |
Output is correct |
28 |
Correct |
121 ms |
21076 KB |
Output is correct |
29 |
Correct |
85 ms |
19020 KB |
Output is correct |
30 |
Correct |
82 ms |
19028 KB |
Output is correct |
31 |
Correct |
86 ms |
20048 KB |
Output is correct |
32 |
Correct |
123 ms |
21072 KB |
Output is correct |
33 |
Correct |
107 ms |
20560 KB |
Output is correct |
34 |
Correct |
61 ms |
17748 KB |
Output is correct |
35 |
Correct |
115 ms |
20816 KB |
Output is correct |
36 |
Correct |
120 ms |
20880 KB |
Output is correct |
37 |
Correct |
69 ms |
17744 KB |
Output is correct |
38 |
Correct |
117 ms |
20096 KB |
Output is correct |
39 |
Correct |
20 ms |
15700 KB |
Output is correct |
40 |
Correct |
116 ms |
20052 KB |
Output is correct |
41 |
Correct |
89 ms |
18880 KB |
Output is correct |
42 |
Correct |
114 ms |
19984 KB |
Output is correct |
43 |
Correct |
41 ms |
16464 KB |
Output is correct |
44 |
Correct |
115 ms |
20108 KB |
Output is correct |
45 |
Correct |
24 ms |
15704 KB |
Output is correct |
46 |
Correct |
116 ms |
20112 KB |
Output is correct |
47 |
Correct |
32 ms |
16208 KB |
Output is correct |
48 |
Correct |
122 ms |
20044 KB |
Output is correct |
49 |
Correct |
250 ms |
24912 KB |
Output is correct |
50 |
Correct |
285 ms |
30288 KB |
Output is correct |
51 |
Correct |
177 ms |
27008 KB |
Output is correct |
52 |
Correct |
271 ms |
30032 KB |
Output is correct |
53 |
Correct |
112 ms |
22348 KB |
Output is correct |
54 |
Correct |
271 ms |
30036 KB |
Output is correct |
55 |
Correct |
228 ms |
28692 KB |
Output is correct |
56 |
Correct |
282 ms |
30304 KB |
Output is correct |
57 |
Correct |
37 ms |
18008 KB |
Output is correct |
58 |
Correct |
269 ms |
30044 KB |
Output is correct |
59 |
Correct |
167 ms |
26352 KB |
Output is correct |
60 |
Correct |
275 ms |
30028 KB |
Output is correct |
61 |
Correct |
183 ms |
28480 KB |
Output is correct |
62 |
Correct |
175 ms |
28552 KB |
Output is correct |
63 |
Correct |
169 ms |
28680 KB |
Output is correct |
64 |
Correct |
150 ms |
29088 KB |
Output is correct |
65 |
Correct |
194 ms |
28876 KB |
Output is correct |
66 |
Correct |
167 ms |
29096 KB |
Output is correct |
67 |
Correct |
177 ms |
28532 KB |
Output is correct |
68 |
Correct |
171 ms |
28484 KB |
Output is correct |
69 |
Correct |
157 ms |
28104 KB |
Output is correct |
70 |
Correct |
170 ms |
28456 KB |
Output is correct |
71 |
Correct |
171 ms |
28364 KB |
Output is correct |
72 |
Correct |
149 ms |
28724 KB |
Output is correct |
73 |
Correct |
447 ms |
35232 KB |
Output is correct |
74 |
Correct |
307 ms |
30956 KB |
Output is correct |
75 |
Correct |
408 ms |
34788 KB |
Output is correct |
76 |
Correct |
535 ms |
38192 KB |
Output is correct |
77 |
Correct |
270 ms |
27964 KB |
Output is correct |
78 |
Correct |
437 ms |
35664 KB |
Output is correct |
79 |
Correct |
497 ms |
36696 KB |
Output is correct |
80 |
Correct |
546 ms |
38180 KB |
Output is correct |
81 |
Correct |
214 ms |
24680 KB |
Output is correct |
82 |
Correct |
404 ms |
34260 KB |
Output is correct |
83 |
Correct |
422 ms |
33872 KB |
Output is correct |
84 |
Correct |
544 ms |
38644 KB |
Output is correct |
85 |
Correct |
315 ms |
32808 KB |
Output is correct |
86 |
Correct |
388 ms |
35676 KB |
Output is correct |
87 |
Correct |
209 ms |
29716 KB |
Output is correct |
88 |
Correct |
392 ms |
36560 KB |
Output is correct |
89 |
Correct |
348 ms |
34268 KB |
Output is correct |
90 |
Correct |
392 ms |
36312 KB |
Output is correct |
91 |
Correct |
249 ms |
31168 KB |
Output is correct |
92 |
Correct |
387 ms |
35736 KB |
Output is correct |
93 |
Correct |
202 ms |
29640 KB |
Output is correct |
94 |
Correct |
385 ms |
35784 KB |
Output is correct |
95 |
Correct |
235 ms |
30660 KB |
Output is correct |
96 |
Correct |
369 ms |
35912 KB |
Output is correct |