#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const ll NMAX = 200001;
const ll INF = (1LL << 58);
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;
int a[NMAX];
int b[NMAX];
unordered_map <int, int> mp;
multiset <int> mst;
int lft[NMAX];
int rgt[NMAX];
int cnt;
int d;
void addRight(int x, int val) {
for(; x > 0; x -= x&(-x))
rgt[x] += val;
}
void addLeft(int x, int val) {
for(; x <= cnt; x += x&(-x))
lft[x] += val;
}
int toRight(int x) {
int val = 0;
for(; x <= cnt; x += x&(-x))
val += rgt[x];
return val;
}
int toLeft(int x) {
int val = 0;
for(; x > 0; x -= x&(-x))
val += lft[x];
return val;
}
void baga(int x) {
auto dupa = mst.lower_bound(x);
if(dupa == mst.begin() && dupa != mst.end()) {
int dr = (*dupa);
int dist = (dr - x);
if(dist < d) {
addLeft(mp[dr], d - dist);
addRight(mp[x], d - dist);
}
} else if(dupa != mst.end()) {
auto inainte = prev(dupa);
int st = (*inainte);
int dr = (*dupa);
int dist = dr - st;
if(dist < d) {
addLeft(mp[dr], -(d - dist));
addRight(mp[st], -(d - dist));
}
dist = dr - x;
if(dist < d) {
addLeft(mp[dr], d - dist);
addRight(mp[x], d - dist);
}
dist = x - st;
if(dist < d) {
addLeft(mp[x], d - dist);
addRight(mp[st], d - dist);
}
} else {
if(mst.size()) {
auto inainte = prev(dupa);
int st = (*inainte);
int dist = (x - st);
if(dist < d) {
addLeft(mp[x], d - dist);
addRight(mp[st], d - dist);
}
}
}
mst.insert(x);
}
int f(int x) {
int dr = 0;
int st = 0;
auto dupa = mst.lower_bound(x);
if(dupa == mst.end()) {
return toLeft(mp[(*prev(dupa))]);
}else{
dr = toRight(mp[(*dupa)]);
}
if(dupa == mst.begin()) {
return toRight(mp[(*dupa)]);
}else{
st = toLeft(mp[(*prev(dupa))]);
}
int dif = (*dupa) - (*prev(dupa));
int adaos = 0, difini = dif;
if(dif < d){
dif = d - dif;
adaos = dr - st + dif;
}
adaos = max(adaos, 0);
adaos = min(adaos, 2 * difini);
return max(2 * st + adaos, 2 * dr + 2 * dif - adaos);
}
int ternary(int a, int b) {
if(a == b) {
return f(a);
}
if(a + 1 == b) {
return min(f(a), f(b));
}
int mid1 = a + (b - a) / 3;
int mid2 = b - (b - a) / 3;
if(f(mid1) < f(mid2)) {
return ternary(a, mid2 - 1);
}
return ternary(mid1 + 1, b);
}
signed main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, i, m, x;
cin >> n >> m >> d;
vector <int> nrm;
for(i = 1; i <= n; i++) {
cin >> a[i];
nrm.push_back(a[i]);
}
for(i = 1; i <= m; i++) {
cin >> b[i];
nrm.push_back(b[i]);
}
int last = -1;
for(auto x : nrm) {
if(x != last) {
cnt++;
}
mp[x] = cnt;
last = x;
}
for(i = 1; i <= n; i++) {
baga(a[i]);
}
for(i = 1; i <= m; i++) {
baga(b[i]);
int sol = ternary((*mst.begin()) - 1, (*prev(mst.end())) + 1);
cout << sol/2;
if(sol%2){
cout << ".5";
}
cout << " ";
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:141:18: warning: unused variable 'x' [-Wunused-variable]
141 | int n, i, m, x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1550 ms |
22624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1550 ms |
22624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
