이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
using namespace std;
mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) {
return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
return a < b ? (a = b, 1) : 0;
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int N = 4e5 + 5;
int n, m;
ll D;
ll a[N];
ll b[N];
ll d[N];
ll suff[N];
int rnd(int l, int r) {
return rng() % (r - l + 1) + l;
}
ll T[N];
ve<ll> Q;
ve<pll> u;
//bool subtask = 1;
//ve<ll> v;
//ve<ll> pos;
//void add(ll x) {
// assert(is_sorted(all(v)));
// int idx = sz(v) - 1;
// fr (i, 0, sz(v) - 1) {
// if (x > v[i]) {
// idx = i - 1;
// break;
// }
// }
//
// ll myPos = -1;
// if (idx - 1 >= 0) {
// myPos = max(x, pos[idx - 1] + D);
// } else {
// myPos = x;
// }
//}
int id[N];
struct Node {
ll last;
ll ans;
};
Node t[4 * N];
//void build(int v, int tl, int tr) {
// t[v] = {-1e18, -1e18};
// if (tl == tr) {
// return;
// }
// int tm = (tl + tr) >> 1;
// build(v << 1, tl, tm);
// build(v << 1 | 1, tm + 1, tr);
//}
//
//void upd(int v, int tl, int tr, int pos) {
// if (tl == tr) {
//
// return;
// }
//}
bool subtask = 1;
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> n >> m >> D;
D *= 2;
fr (i, 1, n) {
cin >> a[i];
// a[i] = rnd(1, int(100));
a[i] *= 2;
}
fr (i, 1, m) {
cin >> b[i];
if (i > 1) {
subtask &= b[i] >= b[i - 1];
}
}
subtask &= n == 0;
if (!subtask) {
fr (i, 1, m) {
ll x;
x = b[i];
x *= 2;
a[++n] = x;
sort(a + 1, a + 1 + n);
ll last = a[1];
ll ans = 0;
fr (j, 2, n) {
if (a[j] - last >= D) {
last = a[j];
continue;
}
umx(ans, abs(a[j] - (last + D)));
last += D;
}
ans /= 2;
cout << ans / 2;
if (ans % 2) cout << ".5";
cout << "\n";
}
} else {
ll last = -1;
ll ans = 0;
fr (i, 1, m) {
ll x;
x = b[i];
x *= 2;
n++;
if (n == 1) {
last = x;
} else {
if (x - last >= D) {
last = x;
} else {
umx(ans, abs(x - (last + D)));
last += D;
}
}
cout << ans / 4;
if ((ans / 4) % 2) cout << ".5";
cout << "\n";
}
}
// fr (i, 1, m) {
// ll x;
// cin >> x;
// x *= 2;
// Q.pb(x);
// u.pb({x, i});
// }
//
// sort(all(u));
// fr (i, 0, sz(u) - 1) {
// id[u[i].se] = i;
// }
//
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |