#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e5;
const long long INF = 1e15;
int x[MAX_N], nrm[MAX_N];
map<int, vector<int>> frecv;
struct info {
long long minn, maxx, maxDiff;
};
struct add {
long long minn, maxx;
};
struct SegTree {
int leftQuery, rightQuery;
info segTree[4 * MAX_N];
add lazy[4 * MAX_N];
void propag( int v, int l, int r ) {
segTree[v].minn += lazy[v].minn;
segTree[v].maxx += lazy[v].maxx;
segTree[v].maxDiff += (lazy[v].minn + lazy[v].maxx) / 2;
if ( l != r ) {
lazy[v * 2 + 1].minn += lazy[v].minn;
lazy[v * 2 + 2].minn += lazy[v].minn;
lazy[v * 2 + 1].maxx += lazy[v].maxx;
lazy[v * 2 + 2].maxx += lazy[v].maxx;
}
lazy[v] = { 0, 0 };
}
void init( int v, int l, int r ) {
if ( l == r ) {
segTree[v] = { INF, -INF, -2 * INF };
return;
}
int mid = (l + r) / 2;
init( v * 2 + 1, l, mid );
init( v * 2 + 2, mid + 1, r );
segTree[v].minn = min( segTree[v * 2 + 1].minn, segTree[v * 2 + 2].minn );
segTree[v].maxx = max( segTree[v * 2 + 1].maxx, segTree[v * 2 + 2].maxx );
segTree[v].maxDiff = max( segTree[v * 2 + 2].maxx - segTree[v * 2 + 1].minn, max( segTree[v * 2 + 1].maxDiff, segTree[v * 2 + 2].maxDiff ) );
}
void init( int l, int r ) {
leftQuery = l;
rightQuery = r;
init( 0, l, r );
}
void update( int v, int l, int r, int lu, int ru, add x ) {
propag( v, l, r );
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
lazy[v] = x;
propag( v, l, r );
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, x );
update( v * 2 + 2, mid + 1, r, lu, ru, x );
segTree[v].minn = min( segTree[v * 2 + 1].minn, segTree[v * 2 + 2].minn );
segTree[v].maxx = max( segTree[v * 2 + 1].maxx, segTree[v * 2 + 2].maxx );
segTree[v].maxDiff = max( segTree[v * 2 + 2].maxx - segTree[v * 2 + 1].minn, max( segTree[v * 2 + 1].maxDiff, segTree[v * 2 + 2].maxDiff ) );
}
void update( int l, int r, add x ) {
update( 0, leftQuery, rightQuery, l, r, x );
}
long long queryAll() {
return segTree[0].maxDiff;
}
} cost;
int main() {
ios_base::sync_with_stdio( false );
cin.tie( NULL );
int n, q, d;
cin >> n >> q >> d;
n += q;
for ( int i = 0; i < n; i++ ) {
cin >> x[i];
frecv[x[i]].push_back( i );
}
int val = 0;
for ( auto p: frecv ) {
for ( int i: p.second )
nrm[i] = ++val;
}
cost.init( 1, n );
for ( int i = 0; i < n; i++ ) {
cost.update( nrm[i], n, { d, d } );
cost.update( nrm[i], nrm[i], { -INF - x[i], INF - x[i] } );
if ( i >= n - q ) {
long long ans = max( 0LL, cost.queryAll() );
cout << ans / 2;
if ( ans % 2 == 1 )
cout << ".5";
cout << " ";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
49568 KB |
Output is correct |
2 |
Correct |
227 ms |
52048 KB |
Output is correct |
3 |
Correct |
171 ms |
31180 KB |
Output is correct |
4 |
Correct |
235 ms |
50140 KB |
Output is correct |
5 |
Correct |
224 ms |
51368 KB |
Output is correct |
6 |
Correct |
228 ms |
50908 KB |
Output is correct |
7 |
Correct |
223 ms |
51536 KB |
Output is correct |
8 |
Correct |
229 ms |
50128 KB |
Output is correct |
9 |
Correct |
226 ms |
50164 KB |
Output is correct |
10 |
Correct |
229 ms |
52524 KB |
Output is correct |
11 |
Correct |
225 ms |
50832 KB |
Output is correct |
12 |
Correct |
222 ms |
51792 KB |
Output is correct |
13 |
Correct |
225 ms |
50004 KB |
Output is correct |
14 |
Correct |
221 ms |
52008 KB |
Output is correct |
15 |
Correct |
223 ms |
51852 KB |
Output is correct |
16 |
Correct |
228 ms |
49892 KB |
Output is correct |
17 |
Correct |
220 ms |
51336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
49568 KB |
Output is correct |
2 |
Correct |
227 ms |
52048 KB |
Output is correct |
3 |
Correct |
171 ms |
31180 KB |
Output is correct |
4 |
Correct |
235 ms |
50140 KB |
Output is correct |
5 |
Correct |
224 ms |
51368 KB |
Output is correct |
6 |
Correct |
228 ms |
50908 KB |
Output is correct |
7 |
Correct |
223 ms |
51536 KB |
Output is correct |
8 |
Correct |
229 ms |
50128 KB |
Output is correct |
9 |
Correct |
226 ms |
50164 KB |
Output is correct |
10 |
Correct |
229 ms |
52524 KB |
Output is correct |
11 |
Correct |
225 ms |
50832 KB |
Output is correct |
12 |
Correct |
222 ms |
51792 KB |
Output is correct |
13 |
Correct |
225 ms |
50004 KB |
Output is correct |
14 |
Correct |
221 ms |
52008 KB |
Output is correct |
15 |
Correct |
223 ms |
51852 KB |
Output is correct |
16 |
Correct |
228 ms |
49892 KB |
Output is correct |
17 |
Correct |
220 ms |
51336 KB |
Output is correct |
18 |
Incorrect |
376 ms |
51780 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |