Submission #333107

#	Time	Username	Problem	Language	Result	Execution time	Memory
333107		CaroLinda	Cake 3 (JOI19_cake3)	C++14	100 / 100	1064 ms	102548 KiB

cake3

#include <bits/stdc++.h>
 
/* 
Porque tú eres lo que necesito
Porque yo soy lo que tú necesitas
Que tu cuerpo es mi lugar favorito
Y tu boca mi comida favorita
 
Tú eres perfecta, sin el 90-60-90
Después de al mundo yo darle la vuelta
Te tenía al lado y no me había dado cuenta
Que tú eres perfecta
 
Quiero que exageres como yo exagero
Y no te me reías porque esto es en serio
 
*/
 
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long
 
const int MAXN = 2e5+10 ;
const ll inf = 1e15 ;
 
using namespace std ;
 
struct PersistentSeg
{
 
	vector<int> sumQtd , lef, rig ;
	vector<ll> sumValues ;
 
	PersistentSeg()
	{
		sumValues.resize(1,0LL) ;
		sumQtd.resize(1,0) ;
		lef.resize(1,0) ;
		rig.resize(1,0) ;
	}
 
	int create( int pos )
	{
		sumValues.push_back( sumValues[pos] ) ;
		sumQtd.push_back( sumQtd[pos] ) ;
		lef.push_back(lef[pos] ) ;
		rig.push_back(rig[pos] ) ;
		return sz(lef)-1 ;
	}
 
	int mid(int l, int r ) { return (l+r)>>1 ; }
 
	int upd(int pos, int l , int r, int x, ll val )
	{
		int newPos = create(pos) , aux ;
		
		sumValues[newPos] += val ;
		sumQtd[newPos]++ ;
 
		if( l == r ) return newPos ;
 
		if( x <= mid(l,r) )
		{
			aux = upd(lef[newPos], l, mid(l,r) , x , val ) ;
			lef[newPos] = aux ;
		}
		else 
		{
			aux = upd(rig[newPos], mid(l,r)+1, r, x, val ) ;
			rig[newPos] = aux ;
		}
 
		return newPos ;
 
	}
 
	ll bb(int posL, int posR, int l, int r , int &m ) //returns the sum of the M bests
	{

		if( m <= 0  ) return 0LL ;
		if( sumQtd[posR]-sumQtd[posL] <= m ) 
		{
			m -= sumQtd[posR]-sumQtd[posL] ;
			return sumValues[posR]-sumValues[posL] ;
		}
 
		ll ar = bb(rig[posL], rig[posR] , mid(l,r)+1, r, m ) ;
		ll al = 0LL ;
 
		if( m ) al = bb(lef[posL], lef[posR], l , mid(l,r), m ) ;
 
		return al + ar ;
 
	}
	
} seg ;
 
int n , m ;
int roots[MAXN] ;
pair<int,int> pieces[MAXN] ;
vector< pair<int,int> > compression ;
ll bestAnswer = -inf ;
 
ll getCost(int l, int r )
{ 
	if(r-l+1 < m ) return -inf ;
	
	int fuel = m ;
 
	ll sumV = -2LL*(pieces[r].first - pieces[l].first );
	sumV += seg.bb(roots[l-1], roots[r], 1, n, fuel ) ;

	return sumV ;
}
 
void solve(int l, int r, int optmin, int optmax )
{
	if( l > r ) return ;
 
	int mid = (l+r)>>1 ;
	int opt = mid ;
	ll valOpt = -inf ;
 
	for(int i = max(optmin, mid) ; i <= optmax ; i++ )
	{
		ll cost = getCost(mid,i) ;
 
		if( cost <= valOpt ) continue ;
 
		valOpt = cost ;
		opt = i ;
 
	}
 
	if(bestAnswer < valOpt ) bestAnswer = valOpt ;
 
	solve(l, mid-1, optmin, opt ) ;
	solve(mid+1, r, opt, optmax ) ; 
}
 
int main()
{
 


	scanf("%d %d", &n, &m ) ;
	for(int i = 1 ; i <= n ; i++ )
		scanf("%d %d", &pieces[i].second, &pieces[i].first ) ;
 
	//I need all of them to be different for simplicity's sake
	//Will this mess things up?
	sort(pieces+1, pieces+1+n) ;

	for(int i = 1 ; i <= n ; i++ ) compression.push_back(make_pair(pieces[i].second,i) ) ;
	sort(all(compression) ) ;

	for(int i = 1 ; i <= n ; i++ ) 
	{
		int idx = lower_bound(all(compression), make_pair(pieces[i].second, i) ) - compression.begin() + 1 ;
		roots[i] = seg.upd(roots[i-1], 1 , n , idx , (ll)pieces[i].second ) ;
	}
 
	solve(1,n-m+1, 1, n) ;

	printf("%lld\n", bestAnswer ) ;
 
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  147 |  scanf("%d %d", &n, &m ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
cake3.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |   scanf("%d %d", &pieces[i].second, &pieces[i].first ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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