// Patryk Niemczyk jln.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long long czytaj(vector<long long> &drzewo, long long v, long long vl, long long vp, long long a, long long b)
{
if (b < a)
return 0;
if (vl >= a && vp <= b)
return drzewo[v];
else if (vl > b || vp < a)
return 0;
else
{
long long mid = (vl + vp) / 2;
return max(czytaj(drzewo, v * 2, vl, mid, a, b), czytaj(drzewo, v * 2 + 1, mid + 1, vp, a, b));
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
long long n;
cin >> n;
vector<pair<long long, long long>> pierwsze(n + 1);
vector<long long> drugie(n);
for (long long i = 0; i <= n; ++i)
{
cin >> pierwsze[i].first;
pierwsze[i].second = i;
}
for (long long i = 0; i < n; ++i)
cin >> drugie[i];
sort(pierwsze.begin(), pierwsze.end());
sort(drugie.begin(), drugie.end());
// for (long long i = 0; i <= n; ++i)
// cout << pierwsze[i].first << " ";
// cout << '\n';
// for (long long i = 0; i < n; ++i)
// cout << drugie[i] << " ";
// cout << '\n';
long long rozmiar = pow(2, ceil(log2(n)));
vector<long long> roz1(2 * rozmiar, 0);
vector<long long> roz2(2 * rozmiar, 0);
for (long long i = rozmiar; i - rozmiar < n; ++i)
{
roz1[i] = pierwsze[i - rozmiar].first - drugie[i - rozmiar];
roz2[i] = pierwsze[i - rozmiar + 1].first - drugie[i - rozmiar];
}
for (long long i = rozmiar - 1; i > 0; --i)
{
roz1[i] = max(roz1[2 * i], roz1[2 * i + 1]);
roz2[i] = max(roz2[2 * i], roz2[2 * i + 1]);
}
// for (long long i = 1; i < roz1.size(); ++i)
// {
// if (i == pow(2, ceil(log2(i))))
// cout << '\n';
// cout << roz1[i] << " ";
// }
// cout << '\n';
// for (long long i = 1; i < roz2.size(); ++i)
// {
// if (i == pow(2, ceil(log2(i))))
// cout << '\n';
// cout << roz2[i] << " ";
// }
// cout << '\n';
vector<long long> odp(n + 1);
for (long long i = 0; i <= n; ++i)
{
// cout << "Max 1 na przedziale: 1 - " << i << ": " << czytaj(roz1, 1, 1, rozmiar, 1, i) << '\n';
// cout << "Max 2 na przedziale: " << i + 1 << " - " << rozmiar << ": " << czytaj(roz2, 1, 1, rozmiar, i + 1, rozmiar) << '\n';
odp[pierwsze[i].second] = max(czytaj(roz1, 1, 1, rozmiar, 1, i), czytaj(roz2, 1, 1, rozmiar, i + 1, rozmiar));
}
for (long long o : odp)
cout << o << " ";
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
352 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
352 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
532 KB |
Output is correct |
| 15 |
Correct |
2 ms |
584 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
2 ms |
592 KB |
Output is correct |
| 18 |
Correct |
2 ms |
524 KB |
Output is correct |
| 19 |
Correct |
1 ms |
592 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
2 ms |
592 KB |
Output is correct |
| 22 |
Correct |
2 ms |
592 KB |
Output is correct |
| 23 |
Correct |
2 ms |
400 KB |
Output is correct |
| 24 |
Correct |
2 ms |
848 KB |
Output is correct |
| 25 |
Correct |
2 ms |
592 KB |
Output is correct |
| 26 |
Correct |
2 ms |
592 KB |
Output is correct |
| 27 |
Correct |
2 ms |
592 KB |
Output is correct |
| 28 |
Correct |
2 ms |
592 KB |
Output is correct |
| 29 |
Correct |
2 ms |
592 KB |
Output is correct |
| 30 |
Correct |
2 ms |
592 KB |
Output is correct |
| 31 |
Correct |
2 ms |
592 KB |
Output is correct |
| 32 |
Correct |
2 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
352 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
532 KB |
Output is correct |
| 15 |
Correct |
2 ms |
584 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
2 ms |
592 KB |
Output is correct |
| 18 |
Correct |
2 ms |
524 KB |
Output is correct |
| 19 |
Correct |
1 ms |
592 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
2 ms |
592 KB |
Output is correct |
| 22 |
Correct |
2 ms |
592 KB |
Output is correct |
| 23 |
Correct |
2 ms |
400 KB |
Output is correct |
| 24 |
Correct |
2 ms |
848 KB |
Output is correct |
| 25 |
Correct |
2 ms |
592 KB |
Output is correct |
| 26 |
Correct |
2 ms |
592 KB |
Output is correct |
| 27 |
Correct |
2 ms |
592 KB |
Output is correct |
| 28 |
Correct |
2 ms |
592 KB |
Output is correct |
| 29 |
Correct |
2 ms |
592 KB |
Output is correct |
| 30 |
Correct |
2 ms |
592 KB |
Output is correct |
| 31 |
Correct |
2 ms |
592 KB |
Output is correct |
| 32 |
Correct |
2 ms |
592 KB |
Output is correct |
| 33 |
Correct |
111 ms |
19624 KB |
Output is correct |
| 34 |
Correct |
123 ms |
20008 KB |
Output is correct |
| 35 |
Correct |
108 ms |
16200 KB |
Output is correct |
| 36 |
Correct |
109 ms |
16524 KB |
Output is correct |
| 37 |
Correct |
111 ms |
20040 KB |
Output is correct |
| 38 |
Correct |
113 ms |
19784 KB |
Output is correct |
| 39 |
Correct |
110 ms |
17736 KB |
Output is correct |
| 40 |
Correct |
113 ms |
18760 KB |
Output is correct |
| 41 |
Correct |
106 ms |
15804 KB |
Output is correct |
| 42 |
Correct |
107 ms |
19016 KB |
Output is correct |
| 43 |
Correct |
107 ms |
18764 KB |
Output is correct |
| 44 |
Correct |
124 ms |
18768 KB |
Output is correct |
| 45 |
Correct |
111 ms |
19016 KB |
Output is correct |
| 46 |
Correct |
106 ms |
18504 KB |
Output is correct |
| 47 |
Correct |
104 ms |
15432 KB |
Output is correct |
| 48 |
Correct |
109 ms |
18760 KB |
Output is correct |
| 49 |
Correct |
112 ms |
19272 KB |
Output is correct |
| 50 |
Correct |
112 ms |
15944 KB |
Output is correct |
| 51 |
Correct |
136 ms |
19272 KB |
Output is correct |
| 52 |
Correct |
111 ms |
15912 KB |
Output is correct |
| 53 |
Correct |
128 ms |
19236 KB |
Output is correct |
