Submission #320171

#TimeUsernameProblemLanguageResultExecution timeMemory
320171Karen124MP3 Player (CEOI10_mp3player)C++14
10 / 100
83 ms2924 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define ll long long int #define F first #define S second #define pb push_back const ll N = 1e5 + 5; const ll LOG = 30; const ll MOD = 1e9 + 7; const ll INF = 1e18 + 10; ll n, Vmax, V2, a[N], t[N], mxT, mxV1; vector <ll> dif; ll R_Do_Operations(ll e, ll T){ for (ll i = n; i >= 2; i--){ if (t[i] - t[i - 1] <= T){ e -= a[i]; } e = max(e, 0ll); e = min(e, Vmax); } return e; } ll Do_Operations(ll s, ll T){ for (ll i = 2; i <= n; i++){ if (t[i] - t[i - 1] <= T){ s += a[i]; } s = max(s, 0ll); s = min(s, Vmax); } return s; } int ok(ll T){ ll s = R_Do_Operations(V2, T); ll e = Do_Operations(s, T); return (e == V2); } int main (){ cin >> n >> Vmax >> V2; for (ll i = 1; i <= n; i++){ char c; cin >> c >> t[i]; a[i] = ((c == '+') ? 1 : -1); if (i != 1) dif.pb(t[i] - t[i - 1]); } if (ok(INF)) return cout << "infinity\n", 0; sort(dif.begin(), dif.end()); dif.resize(unique(dif.begin(), dif.end()) - dif.begin()); ll l = 0, r = dif.size(); while (l + 1 < r){ ll mid = (l + r) / 2; if (!ok(dif[mid])) r = mid; else l = mid; } mxT = dif[r - 1]; ll L = R_Do_Operations(V2, mxT), R = Vmax + 1; while (L + 1 < R){ ll mid = (L + R) / 2; if (Do_Operations(mid, mxT) != V2) R = mid; else L = mid; } mxV1 = R - 1; cout << mxT << ' ' << mxV1 << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...