oj.uz

Submission #445763

# Submission time Handle Problem Language Result Execution time Memory
445763 2021-07-19T14:00:12 Z wind_reaper Candies (JOI18_candies) C++17
100 / 100
 628 ms 27316 KB 
#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;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************

const int64_t INF = 1'000'000'000'000'000'000;

//***************** GLOBAL VARIABLES *****************



//***************** AUXILIARY STRUCTS *****************



//***************** MAIN BODY *****************

void solve(){
	int N;
	cin >> N;

	set<pair<int64_t, int>> s;
	set<int> idx;
	int64_t val[N + 2];
	val[0] = val[N + 1] = -INF;

	s.insert({val[0], 0}), idx.insert(0);
	s.insert({val[N + 1], N + 1}), idx.insert(N + 1);

	for(int i = 1; i <= N; i++){
		cin >> val[i];
		s.insert({val[i], i});
		idx.insert(i);
	}

	int64_t ans = 0;

	for(int i = 1; i <= (N + 1) / 2; i++){
		auto [inc, j] = *s.rbegin();
		s.erase({inc, j}), idx.erase(j);
		ans += inc;
		cout << ans << '\n';

		int l = *prev(idx.lower_bound(j)), r = *idx.upper_bound(j);

		s.erase({val[l], l});
		s.erase({val[r], r});

		idx.erase(r);

		val[l] = val[l] + val[r] - inc;

		s.insert({val[l], l});
	}
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 4 ms 532 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 4 ms 580 KB Output is correct
15 Correct 3 ms 580 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 3 ms 580 KB Output is correct
20 Correct 3 ms 576 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 4 ms 532 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 4 ms 580 KB Output is correct
15 Correct 3 ms 580 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 3 ms 580 KB Output is correct
20 Correct 3 ms 576 KB Output is correct
21 Correct 627 ms 27148 KB Output is correct
22 Correct 601 ms 27268 KB Output is correct
23 Correct 628 ms 27076 KB Output is correct
24 Correct 266 ms 26996 KB Output is correct
25 Correct 271 ms 27040 KB Output is correct
26 Correct 268 ms 26948 KB Output is correct
27 Correct 282 ms 27128 KB Output is correct
28 Correct 304 ms 27100 KB Output is correct
29 Correct 308 ms 27144 KB Output is correct
30 Correct 304 ms 27112 KB Output is correct
31 Correct 330 ms 27316 KB Output is correct
32 Correct 303 ms 27136 KB Output is correct
33 Correct 397 ms 26988 KB Output is correct
34 Correct 431 ms 26952 KB Output is correct
35 Correct 417 ms 27056 KB Output is correct
36 Correct 595 ms 27124 KB Output is correct
37 Correct 616 ms 27192 KB Output is correct
38 Correct 591 ms 27076 KB Output is correct
39 Correct 288 ms 27048 KB Output is correct
40 Correct 265 ms 27012 KB Output is correct
41 Correct 298 ms 27032 KB Output is correct
42 Correct 289 ms 27208 KB Output is correct
43 Correct 286 ms 27296 KB Output is correct
44 Correct 304 ms 27196 KB Output is correct
45 Correct 310 ms 27136 KB Output is correct
46 Correct 340 ms 27140 KB Output is correct
47 Correct 311 ms 27136 KB Output is correct
48 Correct 422 ms 26936 KB Output is correct
49 Correct 438 ms 27020 KB Output is correct
50 Correct 408 ms 26912 KB Output is correct