Submission #1114640

#TimeUsernameProblemLanguageResultExecution timeMemory
1114640AdamGSJust Long Neckties (JOI20_ho_t1)C++17
100 / 100
158 ms7132 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...