#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], b[N], temp[N];
int seg[2][N<<2];
void update( int t, int pos, int val, int l = 1, int r = n, int idx = 1 ) {
if( l == r ) return void( seg[t][idx] = val );
int m = l + r >> 1;
if( pos <= m ) update( t, pos, val, l, m, idx<<1 );
else update( t, pos, val, m + 1, r, idx<<1|1 );
seg[t][idx] = max( seg[t][idx<<1], seg[t][idx<<1|1] );
return ;
}
int query( int t, int ll, int rr, int l = 1, int r = n, int idx = 1 ) {
//printf("t ll rr l r %d %d %d %d %d\n",t,ll,rr,l,r);
if( rr < ll ) return -1e9;
if( l > rr || r < ll ) return -1e9;
if( l >= ll && r <= rr ) return seg[t][idx];
int m = l + r >> 1;
return max( query( t, ll, rr, l, m, idx<<1 ), query( t, ll, rr, m+1, r, idx<<1|1 ) );
}
int main()
{
scanf("%d",&n);
for( int i = 1 ; i <= n + 1 ; i++ ) {
scanf("%d",&a[i]);
temp[i] = a[i];
}
for( int i = 1 ; i <= n ; i++ ) scanf("%d",&b[i]);
sort( a+1, a+2+n ), sort( b+1, b+1+n );
for( int i = 1 ; i <= n ; i++ ) update( 0, i, max( a[i]-b[i], 0 ) );
for( int i = 2 ; i <= n+1 ; i++ ) update( 1, i-1, max( a[i]-b[i-1], 0 ) );
for( int i = 1 ; i <= n+1 ; i++ ) {
int idx = lower_bound( a, a+2+n, temp[i] ) - a;
//printf("%d ",idx);
//printf("%d\n",query( 0, 1, i-1) );
printf("%d ",max( query( 0, 1, idx-1 ), query( 1, idx, n ) ) );
}
return 0;
}
Compilation message
ho_t1.cpp: In function 'void update(int, int, int, int, int, int)':
ho_t1.cpp:12:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
ho_t1.cpp: In function 'int query(int, int, int, int, int, int)':
ho_t1.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
ho_t1.cpp: In function 'int main()':
ho_t1.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
ho_t1.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
ho_t1.cpp:35:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for( int i = 1 ; i <= n ; i++ ) scanf("%d",&b[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
6 ms |
504 KB |
Output is correct |
| 15 |
Correct |
7 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
376 KB |
Output is correct |
| 17 |
Correct |
7 ms |
376 KB |
Output is correct |
| 18 |
Correct |
6 ms |
376 KB |
Output is correct |
| 19 |
Correct |
6 ms |
376 KB |
Output is correct |
| 20 |
Correct |
7 ms |
376 KB |
Output is correct |
| 21 |
Correct |
6 ms |
376 KB |
Output is correct |
| 22 |
Correct |
6 ms |
376 KB |
Output is correct |
| 23 |
Correct |
7 ms |
508 KB |
Output is correct |
| 24 |
Correct |
7 ms |
376 KB |
Output is correct |
| 25 |
Correct |
7 ms |
380 KB |
Output is correct |
| 26 |
Correct |
7 ms |
376 KB |
Output is correct |
| 27 |
Correct |
7 ms |
376 KB |
Output is correct |
| 28 |
Correct |
7 ms |
376 KB |
Output is correct |
| 29 |
Correct |
6 ms |
376 KB |
Output is correct |
| 30 |
Correct |
6 ms |
380 KB |
Output is correct |
| 31 |
Correct |
7 ms |
376 KB |
Output is correct |
| 32 |
Correct |
7 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
6 ms |
504 KB |
Output is correct |
| 15 |
Correct |
7 ms |
376 KB |
Output is correct |
| 16 |
Correct |
5 ms |
376 KB |
Output is correct |
| 17 |
Correct |
7 ms |
376 KB |
Output is correct |
| 18 |
Correct |
6 ms |
376 KB |
Output is correct |
| 19 |
Correct |
6 ms |
376 KB |
Output is correct |
| 20 |
Correct |
7 ms |
376 KB |
Output is correct |
| 21 |
Correct |
6 ms |
376 KB |
Output is correct |
| 22 |
Correct |
6 ms |
376 KB |
Output is correct |
| 23 |
Correct |
7 ms |
508 KB |
Output is correct |
| 24 |
Correct |
7 ms |
376 KB |
Output is correct |
| 25 |
Correct |
7 ms |
380 KB |
Output is correct |
| 26 |
Correct |
7 ms |
376 KB |
Output is correct |
| 27 |
Correct |
7 ms |
376 KB |
Output is correct |
| 28 |
Correct |
7 ms |
376 KB |
Output is correct |
| 29 |
Correct |
6 ms |
376 KB |
Output is correct |
| 30 |
Correct |
6 ms |
380 KB |
Output is correct |
| 31 |
Correct |
7 ms |
376 KB |
Output is correct |
| 32 |
Correct |
7 ms |
376 KB |
Output is correct |
| 33 |
Correct |
327 ms |
8160 KB |
Output is correct |
| 34 |
Correct |
327 ms |
8312 KB |
Output is correct |
| 35 |
Correct |
318 ms |
8312 KB |
Output is correct |
| 36 |
Correct |
323 ms |
8696 KB |
Output is correct |
| 37 |
Correct |
332 ms |
8828 KB |
Output is correct |
| 38 |
Correct |
330 ms |
8696 KB |
Output is correct |
| 39 |
Correct |
327 ms |
7944 KB |
Output is correct |
| 40 |
Correct |
320 ms |
7800 KB |
Output is correct |
| 41 |
Correct |
319 ms |
7928 KB |
Output is correct |
| 42 |
Correct |
329 ms |
8056 KB |
Output is correct |
| 43 |
Correct |
306 ms |
7928 KB |
Output is correct |
| 44 |
Correct |
310 ms |
7544 KB |
Output is correct |
| 45 |
Correct |
324 ms |
7544 KB |
Output is correct |
| 46 |
Correct |
309 ms |
7544 KB |
Output is correct |
| 47 |
Correct |
248 ms |
7416 KB |
Output is correct |
| 48 |
Correct |
249 ms |
7288 KB |
Output is correct |
| 49 |
Correct |
342 ms |
8056 KB |
Output is correct |
| 50 |
Correct |
337 ms |
8056 KB |
Output is correct |
| 51 |
Correct |
342 ms |
7964 KB |
Output is correct |
| 52 |
Correct |
335 ms |
7928 KB |
Output is correct |
| 53 |
Correct |
338 ms |
8184 KB |
Output is correct |
