Submission #1179835

#TimeUsernameProblemLanguageResultExecution timeMemory
1179835anteknneJust Long Neckties (JOI20_ho_t1)C++20
9 / 100
240 ms36028 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define pb push_back #define pll pair<ll, ll> #define st first #define nd second #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define debug false const ll MAXN = 300 * 1000; pll a[MAXN + 1]; pll b[MAXN]; ll wyn[MAXN]; pll akt[MAXN]; vector<pll> v; multiset<ll> s; map<ll, ll> gdzie; int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; for (ll i = 0; i < n + 1; i ++) { cin >> a[i].st; gdzie[a[i].st] = i; a[i].nd = i; } for (ll i = 0; i < n; i ++) { cin >> b[i].st; b[i].nd = i; } sort(a, a + n + 1); sort(b, b + n); for (ll i = 0; i < n + 1; i ++) { v.pb(a[i]); } for (ll i = 0; i < n; i ++) { s.insert(a[i].st - b[i].st); akt[i].st = v[i].st; akt[i].nd = i; } wyn[a[n].nd] = *s.rbegin(); ll pozostaly = a[n].st; for (ll i = 1; i < n + 1; i ++) { auto it = lower_bound(akt, akt + n, make_pair(pozostaly, -1LL)); it --; ll ind = (*it).nd; auto it2 = s.find(akt[ind].st - b[ind].st); s.erase(it2); ll sp = (*it).st; akt[ind].st = pozostaly; pozostaly = sp; s.insert(akt[ind].st - b[ind].st); wyn[gdzie[pozostaly]] = *s.rbegin(); /*for (int i = 0; i < n; i ++) { cout << akt[i].st << " "; } cout << "\n";*/ } for (ll i = 0; i < n + 1; i ++) { cout << max(0LL, wyn[i]) << " "; } cout << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...