Submission #366849

#TimeUsernameProblemLanguageResultExecution timeMemory
366849RainbowbunnyCandies (JOI18_candies)C++17
100 / 100
389 ms19660 KiB
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <chrono> #include <random> #include <bitset> #include <utility> int n; int l[200005], r[200005]; long long a[200005]; std::set <std::pair <long long, int> > S; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); std::cin >> n; a[0] = -1e18; a[n + 1] = -1e18; for(int i = 1; i <= n; i++) { std::cin >> a[i]; S.insert(std::make_pair(-a[i], i)); l[i] = i - 1; r[i] = i + 1; } long long ans = 0; for(int i = 1; i <= (n + 1) / 2; i++) { int id = (*S.begin()).second; S.erase(S.begin()); int left = l[id], right = r[id]; if(left) { S.erase(std::make_pair(-a[left], left)); } if(right != n + 1) { S.erase(std::make_pair(-a[right], right)); } ans += a[id]; if(left != 0) { r[l[left]] = id; l[id] = l[left]; } if(right != n + 1) { l[r[right]] = id; r[id] = r[right]; } a[id] = a[left] + a[right] - a[id]; S.insert(std::make_pair(-a[id], id)); std::cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...