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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tr[1<<19];
int odp[200000];
void zm(int ind,int val){
tr[ind]=val;
ind/=2;
while (ind>0){
tr[ind]=max(tr[ind*2],tr[ind*2+1]);
ind/=2;
}
}
int main()
{
int n,dltr=1;
cin >> n;
while (dltr<n) dltr*=2;
vector<pair<int,int>> a(n+1);
vector<int> b(n);
for (int i=0; i<n+1; i++){
cin >> a[i].first;
a[i].second=i;
}
for (int i=0; i<n; i++) cin >> b[i];
sort(a.begin(),a.end());
sort(b.begin(),b.end());
//for (int i=0; i<n+1; i++) cout << a[i].first << ' ' << a[i].second << '\n';
for (int i=0; i<n; i++) tr[dltr+i]=max(a[i+1].first-b[i],0);
for (int i=dltr-1; 0<i; i--) tr[i]=max(tr[i*2],tr[i*2+1]);
//for (int i=0; i<dltr*2; i++) cout << tr[i] <<' ';
//cout << '\n';
odp[a[0].second]=tr[1];
for (int i=0; i<n; i++){
zm(i+dltr,a[i].first-b[i]);
//for (int i=0; i<dltr*2; i++) cout << tr[i] <<' ';
//cout << '\n';
odp[a[i+1].second]=tr[1];
}
for (int i=0; i<n+1; i++) cout << odp[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... |