oj.uz

Submission #247492

# Submission time Handle Problem Language Result Execution time Memory
247492 2020-07-11T13:24:36 Z RealSuperman1 Candies (JOI18_candies) C++17
100 / 100
 1184 ms 52584 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragme GCC target("avx2");
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
//#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fsdalfjlas x1
#define djfdslfka y1


using namespace std;
using namespace __gnu_pbds;

/*
	st.insert(k);
	st.find_by_order(k); iterator on k-th from 0
	st.order_of_key(k); strictly less than k
*/

typedef
tree<
  ll,
  null_type,
  less_equal<ll>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;


const ll mod = 1e9 + 7;


inline int modulo(int x) {x %= mod; return (x + mod) % mod; }
inline int mult(int x, int y) { ll x1 = modulo(x), y1 = modulo(y); return (x1 * y1) % (mod * 1ll); }
//inline void add(int &x, int y) { x = modulo(x + y); }
inline void Max(int &x, int y) { x = max(x, y); }
inline void Min(int &x, int y) { x = min(x, y); }


const int blocksz = 300;
const int inf = 1e9;
const ll INF = 1e16 + 2;
const int N = 2e5 + 123;
const int M = 2e5 + 10;
const int LIM = 1000000000;


ll n, a[N], ans = 0;
set <pair<ll, pll>> s;
set <ll> R;
map <ll, ll> L;
map <pll, ll> val;


main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	cin.tie(NULL); cout.tie(NULL);
//	freopen("input.txt", "r", stdin);
//	freopen("input.in", "r", stdin);
//	freopen("input.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	a[0] = a[n + 1] = -INF;
	for (int i = 0; i <= n + 1; i++) {
		R.insert(i);
		L[i] = i;
		s.insert({-a[i], {i, i}});
		val[{i, i}] = a[i];
	}
	for (int i = 1; i <= (n + 1) / 2; i++) {
		pair<ll, pll> tmp = *s.begin();
		tmp.fi = -tmp.fi;
		ans += tmp.fi;
		ll l1, r1, l2, r2, l, r, v, v1, v2;
		l = tmp.se.fi; r = tmp.se.se;
		r1 = l - 1; l1 = L[r1];
		r2 = *R.lower_bound(r + 1); l2 = L[r2];
		v = val[{l, r}]; v1 = val[{l1, r1}]; v2 = val[{l2, r2}];
		val.erase({l, r}); val.erase({l1, r1}); val.erase({l2, r2});
		L.erase(r); L.erase(r1); L.erase(r2);
		R.erase(r); R.erase(r1); R.erase(r2);
		s.erase({-v, {l, r}}); s.erase({-v1, {l1, r1}}); s.erase({-v2, {l2, r2}});
		s.insert({-(v1 + v2 - v), {l1, r2}});
		R.insert(r2);
		L[r2] = l1;
		val[{l1, r2}] = v1 + v2 - v;
		cout << ans << "\n";
	}
}

Compilation message

candies.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
8.0 / 8.0

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

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 9 ms 896 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 9 ms 896 KB Output is correct
8 Correct 9 ms 896 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 9 ms 896 KB Output is correct
12 Correct 10 ms 896 KB Output is correct
13 Correct 9 ms 896 KB Output is correct
14 Correct 10 ms 896 KB Output is correct
15 Correct 9 ms 896 KB Output is correct
16 Correct 8 ms 896 KB Output is correct
17 Correct 9 ms 896 KB Output is correct
18 Correct 8 ms 896 KB Output is correct
19 Correct 8 ms 896 KB Output is correct
20 Correct 8 ms 896 KB Output is correct
21 Correct 1184 ms 52344 KB Output is correct
22 Correct 1135 ms 52584 KB Output is correct
23 Correct 1158 ms 52488 KB Output is correct
24 Correct 534 ms 52216 KB Output is correct
25 Correct 543 ms 52152 KB Output is correct
26 Correct 535 ms 52088 KB Output is correct
27 Correct 553 ms 52416 KB Output is correct
28 Correct 576 ms 52344 KB Output is correct
29 Correct 558 ms 52344 KB Output is correct
30 Correct 580 ms 52344 KB Output is correct
31 Correct 588 ms 52448 KB Output is correct
32 Correct 591 ms 52444 KB Output is correct
33 Correct 805 ms 52088 KB Output is correct
34 Correct 763 ms 52344 KB Output is correct
35 Correct 796 ms 52216 KB Output is correct
36 Correct 1104 ms 52344 KB Output is correct
37 Correct 1160 ms 52344 KB Output is correct
38 Correct 1132 ms 52260 KB Output is correct
39 Correct 529 ms 52088 KB Output is correct
40 Correct 515 ms 52216 KB Output is correct
41 Correct 530 ms 52088 KB Output is correct
42 Correct 556 ms 52344 KB Output is correct
43 Correct 559 ms 52396 KB Output is correct
44 Correct 550 ms 52472 KB Output is correct
45 Correct 590 ms 52472 KB Output is correct
46 Correct 582 ms 52432 KB Output is correct
47 Correct 610 ms 52356 KB Output is correct
48 Correct 794 ms 52216 KB Output is correct
49 Correct 804 ms 52216 KB Output is correct
50 Correct 786 ms 52316 KB Output is correct