제출 #245425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245425		arnold518	Candies (JOI18_candies)	C++14	0 / 100	8 ms	640 KiB

candies

#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;
		assert(A[l]==S.begin()->first);

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

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

컴파일 시 표준 에러 (stderr) 메시지

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]);
                         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92