oj.uz

Submission #401355

# Submission time Handle Problem Language Result Execution time Memory
401355 2021-05-10T01:29:01 Z arwaeystoamneg Candies (JOI18_candies) C++17
100 / 100
 118 ms 10292 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
int n;
const int MAX = 200005;
ll a[MAX];
int l[MAX], r[MAX];
int main()
{
	setIO("test1");
	cin >> n;

	F0R(i, n)cin >> a[i];
	priority_queue<pll>todo;
	F0R(i, n)todo.push({ a[i],i });
	FOR(i, 1, n)l[i] = i - 1;
	F0R(i, n - 1)r[i] = i + 1;
	l[0] = r[n - 1] = -1;
	ll ans = 0;
	FOR(k, 1, (n + 3) / 2)
	{
		int i;
		while (1)
		{
			i = todo.top().s;
			if (a[i] != todo.top().f)
			{
				todo.pop();
			}
			else
			{
				break;
			}
		}
		ans += a[i];
		cout << ans << endl;
		if (l[i] != -1 && r[i] != -1)
		{
			a[i] = a[l[i]] + a[r[i]] - a[i];
			if (a[i] < -linf)a[i] = -linf;
		}
		else
		{
			a[i] = -linf;
		}
		a[l[i]] = a[r[i]] = -linf;
		if (l[i] != -1 && l[l[i]] != -1)r[l[l[i]]] = i;
		if (r[i] != -1 && r[r[i]] != -1)l[r[r[i]]] = i;
		r[i] = r[r[i]];
		l[i] = l[l[i]];
		todo.push({ a[i],i });;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 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 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 105 ms 10092 KB Output is correct
22 Correct 115 ms 10056 KB Output is correct
23 Correct 118 ms 10292 KB Output is correct
24 Correct 85 ms 9992 KB Output is correct
25 Correct 86 ms 10000 KB Output is correct
26 Correct 85 ms 9928 KB Output is correct
27 Correct 106 ms 10140 KB Output is correct
28 Correct 94 ms 10056 KB Output is correct
29 Correct 91 ms 10160 KB Output is correct
30 Correct 99 ms 10184 KB Output is correct
31 Correct 90 ms 10160 KB Output is correct
32 Correct 94 ms 10160 KB Output is correct
33 Correct 98 ms 9932 KB Output is correct
34 Correct 96 ms 9904 KB Output is correct
35 Correct 95 ms 9904 KB Output is correct
36 Correct 115 ms 10032 KB Output is correct
37 Correct 106 ms 10240 KB Output is correct
38 Correct 103 ms 10028 KB Output is correct
39 Correct 84 ms 9904 KB Output is correct
40 Correct 110 ms 9908 KB Output is correct
41 Correct 84 ms 9944 KB Output is correct
42 Correct 92 ms 10164 KB Output is correct
43 Correct 111 ms 10112 KB Output is correct
44 Correct 93 ms 10044 KB Output is correct
45 Correct 96 ms 10120 KB Output is correct
46 Correct 98 ms 10064 KB Output is correct
47 Correct 92 ms 10152 KB Output is correct
48 Correct 103 ms 9900 KB Output is correct
49 Correct 105 ms 9972 KB Output is correct
50 Correct 104 ms 9844 KB Output is correct