Submission #1172039

#TimeUsernameProblemLanguageResultExecution timeMemory
1172039coolboy19521Bigger segments (IZhO19_segments)C++20
100 / 100
134 ms14236 KiB
#include "bits/stdc++.h" #define mxN 500005 using namespace std; long long pr[mxN]; int a[mxN]; int main(){ int N; cin >> N; for (int i = 1; i <= N; i ++) cin >> a[i]; priority_queue<tuple<long long,int,int>> pq; long long aux = 0; int ans = 0; pair<int,int> bs = {0, 0}; for (int i = 1; i <= N; i ++){ pr[i] = aux += a[i]; for(;;){ if (pq.empty()) break; auto [sm, cn, ix] = pq.top(); sm = -sm; if (sm - aux <= 0){ bs = max(bs, {cn, ix}); pq.pop(); } else break; } auto [cn, ix] = bs; ans = cn + 1; pq.emplace(pr[ix] - pr[i] - aux, cn + 1, i); } cout << ans << endl; }
#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...