This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long
#define mod 1000000007
ofstream fout(".out");
ifstream fin(".in");
int N, Left, Right;
int seg1[600000], seg2[600000];
int get_max1(int l = 1, int r = N, int ind = 1) {
if(l > Right || r < Left)
return 0;
if(l >= Left && r <= Right)
return seg1[ind];
int mid = (l + r) / 2;
return max(get_max1(l, mid, ind * 2), get_max1(mid + 1, r, ind * 2 + 1));
}
int get_max2(int l = 1, int r = N, int ind = 1) {
if(l > Right || r < Left)
return 0;
if(l >= Left && r <= Right)
return seg2[ind];
int mid = (l + r) / 2;
return max(get_max2(l, mid, ind * 2), get_max2(mid + 1, r, ind * 2 + 1));
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
N = exp2(ceil(log2(n)));
int b[n];
vector<pair<int, int>> a;
for(int i = 0; i < n + 1; i++) {
int x;
cin >> x;
a.push_back({x, i});
}
sort(a.begin(), a.end());
for(int i = 0; i < n; i++)
cin >> b[i];
sort(b, b + n);
for(int i = 0; i < n; i++) {
seg1[i + N] = max(0, a[i].first - b[i]);
seg2[i + N] = max(0, a[i + 1].first - b[i]);
}
for(int i = N - 1; i >= 1; i--) {
seg1[i] = max(seg1[i * 2], seg1[i * 2 + 1]);
seg2[i] = max(seg2[i * 2], seg2[i * 2 + 1]);
}
int ans[n + 1] = {};
for(int i = 0; i < n + 1; i++) {
if(i) {
Left = 1, Right = i;
ans[a[i].second] = max(ans[a[i].second], get_max1());
}
Left = i + 1, Right = n;
ans[a[i].second] = max(ans[a[i].second], get_max2());
}
for(int i = 0; i < n + 1; i++)
cout << ans[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... |