Submission #503522

#TimeUsernameProblemLanguageResultExecution timeMemory
503522Koosha_mvCandies (JOI18_candies)C++14
100 / 100
430 ms22328 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first #define int ll const int N=1e6+99,S=2,inf=1e16; int n,t,ans,a[N],res[N],ps[N][S],L[N],R[N]; set<pair<int,pair<int,int> > > s; void Add(int l,int r){ if(r>n || l<1) return ; int res=(ps[r][1]-ps[l-1][0])-(ps[r][0]-ps[l-1][1]); s.insert({res,{l,r}}); } void del(int l,int r){ if(r>n || l<1) return ; int res=(ps[r][1]-ps[l-1][0])-(ps[r][0]-ps[l-1][1]); s.erase({res,{l,r}}); } main(){ cin>>n; f(i,2,n+2){ cin>>a[i]; } n+=2; a[1]=-inf; a[n]=-inf; f(i,1,n+1){ L[i]=R[i]=i; s.insert({a[i],{L[i],R[i]}}); ps[i][0]=ps[i-1][1]; ps[i][1]=ps[i-1][0]+a[i]; } f(t,0,(n+1)/2-1){ pair<int,pair<int,int> > p=*s.rbegin(); int copy,l=p.S.F-1,r=p.S.S+1; R[l+1]=0,L[r-1]=0; s.erase(p); ans+=p.F; copy=l; del(L[l],l); l=L[l]; L[copy]=0,R[copy]=0; R[l]=r; copy=r; del(r,R[r]); r=R[r]; L[copy]=0,R[copy]=0; L[r]=l; Add(l,r); R[l]=r; L[r]=l; cout<<ans<<" "; } }

Compilation message (stderr)

candies.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...