// ~ Be Name Khoda ~
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 20;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
ll d, x[maxn5];
int per[maxn5], pos[maxn5];
struct corona{
bool empty;
ll max_time, last_pos, first_pos;
corona(){
empty = true;
}
} seg[maxnt];
corona operator +(corona a, corona b){
if(a.empty)
return b;
if(b.empty)
return a;
corona ans;
ans.empty = false;
ll shifta = 0, shiftb = 0;
if(d <= b.first_pos - a.last_pos){
ll can = b.first_pos - a.last_pos - d;
if(a.max_time < b.max_time)
shifta = min(can, b.max_time - a.max_time);
if(b.max_time < a.max_time)
shiftb = min(can, a.max_time - b.max_time) * -1;
}
else{
ll need = d - (b.first_pos - a.last_pos);
if(a.max_time < b.max_time){
shifta = min(need, b.max_time - a.max_time);
shifta *= -1;
need += shifta;
}
if(a.max_time > b.max_time){
shiftb = min(need, a.max_time - b.max_time);
need -= shiftb;
}
need /= 2;
shifta -= need;
shiftb += need;
}
//cout << "look " << a.max_time << ' ' << a.first_pos << ' ' << a.last_pos << endl;
//cout << b.max_time << ' ' << b.first_pos << ' ' << b.last_pos << endl;
//cout << "ok " << shifta << ' ' << shiftb << ' ' << endl;
ans.max_time = max(a.max_time + abs(shifta), b.max_time + abs(shiftb));
ans.last_pos = b.last_pos + shiftb;
ans.first_pos = a.first_pos + shifta;
return ans;
}
inline bool cmp(int i, int j){return x[i] < x[j];}
void add(int l, int r, int id, int v){
if(r - l == 1){
seg[v].empty = false;
seg[v].max_time = 0;
seg[v].last_pos = seg[v].first_pos = x[per[l]];
return;
}
int mid = (l + r) >> 1;
if(id < mid)
add(l, mid, id, v * 2);
else
add(mid, r, id, v * 2 + 1);
seg[v] = seg[v * 2] + seg[v * 2 + 1];
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m >> d;
d *= 2;
for(int i = 0; i < n; i++){
cin >> x[i];
x[i] *= 2;
per[i] = i;
}
for(int i = n; i < m + n; i++){
cin >> x[i];
x[i] *= 2;
per[i] = i;
}
sort(per, per + n + m, cmp);
for(int i = 0; i < n + m; i++)
pos[per[i]] = i;
for(int i = 0; i < n; i++)
add(0, n + m, pos[i], 1);
for(int i = 0; i < m; i++){
add(0, n + m, pos[i + n], 1);
cout << seg[1].max_time / 2;
if(seg[1].max_time & 1)
cout << ".5";
cout << ' ';
}
cout << endl;
}
/*
0 3 2
1 3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
15 ms |
37856 KB |
Output is correct |
| 3 |
Correct |
16 ms |
37912 KB |
Output is correct |
| 4 |
Correct |
19 ms |
37856 KB |
Output is correct |
| 5 |
Correct |
16 ms |
37916 KB |
Output is correct |
| 6 |
Correct |
15 ms |
37916 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
37848 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
37844 KB |
Output is correct |
| 2 |
Correct |
15 ms |
37856 KB |
Output is correct |
| 3 |
Correct |
16 ms |
37912 KB |
Output is correct |
| 4 |
Correct |
19 ms |
37856 KB |
Output is correct |
| 5 |
Correct |
16 ms |
37916 KB |
Output is correct |
| 6 |
Correct |
15 ms |
37916 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
37848 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
42320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
42320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
