Submission #126034

#	Time	Username	Problem	Language	Result	Execution time	Memory
126034		TadijaSebez	Cake 3 (JOI19_cake3)	C++11	5 / 100	5 ms	1144 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll inf=1e18;
const int N=200050;
const int M=18*N;
int v[N],c[N],id[N],idv[N],pos[N],n,m;
int ls[M],rs[M],tsz,root[N],sz[M];
ll sum[M];
void Set(int p, int &c, int ss, int se, int qi, ll x)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+x;sz[c]=sz[p]+1;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,x);
	else Set(rs[p],rs[c],mid+1,se,qi,x);
}
ll Get(int p, int c, int ss, int se, int k)
{
	if(ss==se) return k>0?sum[c]:0;
	int mid=ss+se>>1;
	int A=sz[ls[c]]-sz[ls[p]];
	ll B=sum[ls[c]]-sum[ls[p]];
	if(A<=k) return B+Get(rs[p],rs[c],mid+1,se,k-A);
	else return Get(ls[p],ls[c],ss,mid,k);
}
map<pair<int,int>,ll> dp;
ll Get(int l, int r)
{
	if(dp.count({l,r})) return dp[{l,r}];
	return dp[{l,r}]=v[id[l]]+c[id[l]]+v[id[r]]-c[id[r]]+Get(root[l],root[r-1],1,n,m-2);
}
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return c[i]<c[j];});
	sort(idv+1,idv+1+n,[&](int i, int j){ return v[i]>v[j];});
	for(int i=1;i<=n;i++) pos[idv[i]]=i;
	for(int i=1;i<=n;i++) Set(root[i-1],root[i],1,n,pos[id[i]],v[id[i]]);
	vector<int> L,R;
	for(int i=1;i<=n;i++) if(i==1 || v[id[i]]+c[id[i]]>v[id[L.back()]]+c[id[L.back()]]) L.pb(i);
	for(int i=n;i>=1;i--) if(i==n || v[id[i]]-c[id[i]]>v[id[R.back()]]-c[id[R.back()]]) R.pb(i);
	reverse(R.begin(),R.end());
	ll ans=-inf;
	deque<int> dq;
	for(int i=0,j=0;i<R.size();i++)
	{
		while(j<L.size() && R[i]-L[j]+1>=m)
		{
			while(dq.size() && Get(L[j],R[i])>=Get(dq.back(),R[i])) dq.pop_back();
			dq.push_back(L[j]);
			j++;
		}
		while(dq.size()>1 && Get(dq[1],R[i])>=Get(dq[0],R[i])) dq.pop_front();
		if(dq.size()) ans=max(ans,Get(dq.front(),R[i]));
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void Set(int, int&, int, int, int, long long int)':
cake3.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake3.cpp: In function 'long long int Get(int, int, int, int, int)':
cake3.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<R.size();i++)
                  ~^~~~~~~~~
cake3.cpp:50:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<L.size() && R[i]-L[j]+1>=m)
         ~^~~~~~~~~
cake3.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:37:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76