Submission #213433

#	Time	Username	Problem	Language	Result	Execution time	Memory
213433		GioChkhaidze	Candies (JOI18_candies)	C++14	100 / 100	514 ms	19460 KiB

candies

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,y,nx,pr,pre[N],nex[N];
ll ans,a[N];
set < pair < ll , int > > st;
set < pair < ll , int > > :: iterator it;
main () {
 cin>>n;
 pre[0]=-1,nex[0]=1;
 pre[n+1]=n,nex[n+1]=n+2;
 for (int i=1; i<=n; i++) {
  cin>>a[i];
  st.insert({a[i],i});
  pre[i]=i-1,nex[i]=i+1;
 }
 a[0]=a[n+1]=-1e15;
 for (int i=1; i<=(n+1)/2; i++) {
  it=st.end(); --it;
  y=(*it).second;
  pr=pre[y],nx=nex[y];
  st.erase({a[y],y});
  ans+=a[y],a[y]=-a[y]; 

  if (pr!=-1) {
   a[y]+=a[pr];
   nex[pre[pr]]=y,pre[y]=pre[pr];
   st.erase({a[pr],pr});
  }
	
  if (nx!=n+2) {
   a[y]+=a[nx];
   nex[y]=nex[nx],pre[nex[nx]]=y;
   st.erase({a[nx],nx});
  }
  
  st.insert({a[y],y});
  cout<<ans<<"\n";
 }
}

Compilation message (stderr)

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

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