Submission #245423

# Submission time Handle Problem Language Result Execution time Memory
245423 2020-07-06T11:43:27 Z arnold518 Candies (JOI18_candies) C++14
0 / 100
7 ms 640 KB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e16;

int N;
ll A[MAXN+10], ans;

set<int> L, R;
set<pll, greater<pll>> S;

pii f(int x)
{
	int l, r;
	r=*R.lower_bound(x);
	l=*(--L.upper_bound(x));
	return {l, r};
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<=N; i++) scanf("%lld", &A[i]);
    for(i=0; i<=N+1; i++) L.insert(i), R.insert(i);
	for(i=1; i<=N; i++) S.insert({A[i], i});

	for(i=1; i<=(N+1)/2; i++)
	{
		ans+=S.begin()->first;
		printf("%lld\n", ans);
		int x=S.begin()->second;

		int l=f(x).first, r=f(x).second, pl=f(l-1).first, pr=f(l-1).second, ql=f(r+1).first, qr=f(r+1).second;

		if(l!=1 && r!=N)
		{
			L.erase(l), R.erase(r), S.erase({A[l], l});
			L.erase(pl), R.erase(pr), S.erase({A[pl], pl});
			L.erase(ql), R.erase(qr), S.erase({A[ql], ql});

			L.insert(pl); R.insert(qr);
			A[pl]=A[pl]+A[ql]-A[l];
			S.insert({A[pl], pl});
		}
	}
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:27:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
candies.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
candies.cpp:30:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%lld", &A[i]);
                         ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -