Submission #128497

#	Time	Username	Problem	Language	Result	Execution time	Memory
128497		Lawliet	Cake 3 (JOI19_cake3)	C++14	100 / 100	1676 ms	129920 KiB

cake3

#include <bits/stdc++.h>

#define MAX 200010
#define MAXV 1000000010
#define INF 1000000000000000000LL

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

class PersistentSegmentTree
{
	public:

		void copy(int node)
		{
			e.push_back( e[node] );
			d.push_back( d[node] );

			qtd.push_back( qtd[node] );

			sum.push_back( sum[node] );
		}

		int update(int node, int l, int r, int i)
		{
			int newNode = ++curNode;
			copy( node );

			if(l == r)
			{
				qtd[newNode]++;
				sum[newNode] += i;

				return newNode;
			}

			int m = (l + r)/2;

			if(i <= m)
			{
				int aux = update(e[newNode] , l , m , i);
				e[newNode] = aux;
			}
			else
			{
				int aux = update(d[newNode] , m + 1 , r , i);
				d[newNode] = aux;
			}

			qtd[newNode] = qtd[ e[newNode] ] + qtd[ d[newNode] ];
			sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];

			return newNode;
		}

		lli bs(int nodeL, int nodeR, int l, int r, lli k)
		{
			if(l == r) return k*l;

			int m = (l + r)/2;

			int qtdRight = qtd[ d[nodeR] ] - qtd[ d[nodeL] ];
			lli sumRight = sum[ d[nodeR] ] - sum[ d[nodeL] ];

			if(k <= qtdRight) return bs(d[nodeL] , d[nodeR] , m + 1 , r , k);
			return bs(e[nodeL] , e[nodeR] , l , m , k - qtdRight) + sumRight;
		}

		lli getHighests(int l, int r, int k)
		{
			return bs(root[l - 1] , root[r] , 0 , MAXV , k);
		}

		void update(int v)
		{
			curVersion++;

			root[curVersion] = update(root[curVersion - 1] , 0 , MAXV , v);
		}

		PersistentSegmentTree()
		{
			e.push_back( 0 ); d.push_back( 0 );
			qtd.push_back( 0 ); sum.push_back( 0LL );

			copy( 0 );

			root[0] = 1;

			curNode = 1;
		}

	private:

		int curNode;
		int curVersion;

		int root[MAX];

		vector<int> e, d;
		vector<int> qtd;

		vector<lli> sum;
};

int n, m;
int n1, n2;

int C[MAX];
int V[MAX];

lli ans[MAX];

vector<pii> aux;

PersistentSegmentTree SEG;

void DivAndConquer(int l, int r, int optmin, int optmax)
{
	if(l > r) return;

	int mid = (l + r)/2;

	int optInd = optmin;
	lli optAns = -INF;

	for(int g = max(mid + m - 1 , optmin) ; g <= optmax ; g++)
	{
		lli curAns = SEG.getHighests(mid + 1 , g - 1 , m - 2) - 2*C[g] + V[g];

		if(curAns > optAns)
		{
			optInd = g;
			optAns = curAns;
		}
	}

	ans[ mid ] = optAns + V[mid] + 2*C[mid];

	DivAndConquer(l , mid - 1 , optmin , optInd);
	DivAndConquer(mid + 1 , r , optInd , optmax);
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d %d",&n1,&n2);

		aux.push_back({n2 , n1});
	}

	sort(aux.begin() , aux.end());

	for(int g = 0 ; g < n ; g++)
	{
		C[g + 1] = aux[g].first;
		V[g + 1] = aux[g].second;

		SEG.update( V[g + 1] );
	}

	DivAndConquer(1 , n - m + 1 , 1 , n);

	lli mx = -INF;

	for(int g = 1 ; g <= n - m + 1 ; g++)
		mx = max(mx , ans[g]);

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

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]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n1,&n2);
   ~~~~~^~~~~~~~~~~~~~~~~

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