Submission #1266309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266309		PlayVoltz	Cake 3 (JOI19_cake3)	C++20	100 / 100	657 ms	11380 KiB

cake3

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <iostream>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair

int n, m, ans=LLONG_MIN, R=1, L=1;
vector<pii> vect, temp;
vector <int> ft, disc, ft2;

int query(int index){
	int sum = 0;
	while (index>0){
		sum+=ft[index];
		index-= index & (-index);
	}
	return sum;
}

void update(int index, int val){
	while (index<=n){
		ft[index]+=val;
		index+=index&(-index);
	}
}

int query2(int index){
	int sum = 0;
	while (index>0){
		sum+=ft2[index];
		index-= index & (-index);
	}
	return sum;
}

void update2(int index, int val){
	while (index<=n){
		ft2[index]+=val;
		index+=index&(-index);
	}
}

int f(int l, int r){
	if (r-l+1<m)return LLONG_MIN/2;
	while (L>l)--L, update(disc[L], vect[L].second), update2(disc[L], 1);
	while (R<r)++R, update(disc[R], vect[R].second), update2(disc[R], 1);
	while (L<l)update(disc[L], -vect[L].second), update2(disc[L], -1), ++L;
	while (R>r)update(disc[R], -vect[R].second), update2(disc[R], -1), --R;
	int low=0, high=n+1;
	while (low+1<high){
		int mid=(low+high)/2;
		if (query2(mid)<=m)low=mid;
		else high=mid;
	}
	return query(low);
}

void dnc(int l, int r, int optl, int optr){
	if (l>r)return;
	int best=LLONG_MIN/2, opt=1, mid=(l+r)/2;
	for (int i=min(mid, optr); i>=optl; --i){
		int res=f(i, mid)-2*(vect[mid].first-vect[i].first);
		if (res>best)best=res, opt=i;
	}
	ans=max(ans, best);
	dnc(l, mid-1, optl, opt);
	dnc(mid+1, r, opt, optr);
}

int32_t main(){
	cin>>n>>m;
	vect.resize(n+1, mp(LLONG_MIN/2, LLONG_MIN/2));
	disc.resize(n+1);
	ft.resize(n+1, 0);
	ft2.resize(n+1, 0);
	temp.resize(n);
	for (int i=1; i<=n; ++i)cin>>vect[i].second>>vect[i].first;
	sort(vect.begin(), vect.end());
	for (int i=1; i<=n; ++i)temp[i-1]=mp(vect[i].second, i);
	sort(temp.begin(), temp.end(), greater<pii>());
	for (int i=0; i<n; ++i)disc[temp[i].second]=i+1;
	L=R=temp[0].second;
	update(1, temp[0].first);
	update2(1, 1);
	dnc(1, n, 1, n);
	cout<<ans;
}

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