Submission #411079

#	Time	Username	Problem	Language	Result	Execution time	Memory
411079		alireza_kaviani	Cake 3 (JOI19_cake3)	C++11	100 / 100	1002 ms	26708 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = (1 << 20);
const ll LOG = 20;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , m , curl = 1 , curr = 0 , V[MAXN] , C[MAXN] , val[MAXN] , ans[MAXN] , fen[2][MAXN];
vector<pll> vec , compress;

void add(int ind , int x , int val){
	for(x++; x < MAXN ; x += x & -x)	fen[ind][x] += val;
}

ll get(int ind , int x){
	ll ans = 0;
	for(x++; x ; x -= x & -x)	ans += fen[ind][x];
	return ans;
}

ll find(ll val){
	int ans = 0;
	for(int i = LOG - 1 ; i >= 0 ; i--){
		if(fen[0][ans + (1 << i)] < val){
			val -= fen[0][ans + (1 << i)];
			ans += (1 << i);
		}
	}
	return ans;
}

ll calc(){
	int ind = find(m - 2);
	return get(1 , ind);
}

void insert(int i , int x){
	add(0 , val[i] , 1 * x);
	add(1 , val[i] , V[i] * x);
//	cout << i << sep << x << sep << calc() << endl;
}

void move(int l , int r){
	while(curr < r)	insert(++curr , 1);
	while(l < curl)	insert(--curl , 1);
	while(r < curr)	insert(curr-- , -1);
	while(curl < l)	insert(curl++ , -1);
}

void solve(int l , int r , int optl , int optr){
	if(r < l)	return;
	int mid = l + r >> 1 , opt = -1;
	for(int i = optl ; i <= min(optr , mid - (int)m + 1) ; i++){
		move(i + 1 , mid - 1);
//		cout << i << sep << mid << sep << sum << endl;
		ll sum = calc();
		if(sum + V[mid] + V[i] - C[mid] + C[i] > ans[mid]){
			ans[mid] = sum + V[mid] - C[mid] + V[i] + C[i];
			opt = i;
		}
	}
	solve(l , mid - 1 , optl , opt);
	solve(mid + 1 , r , opt , optr);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	fill(ans , ans + MAXN , -INF);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i++){
		cin >> V[i] >> C[i];
		vec.push_back({C[i] , V[i]});
	}
	sort(all(vec));
	for(int i = 1 ; i <= n ; i++){
		C[i] = vec[i - 1].X * 2;
		V[i] = vec[i - 1].Y;
		compress.push_back({V[i] , i});
	}
	sort(all(compress) , greater<pll>());
	for(int i = 0 ; i < n ; i++){
		val[compress[i].Y] = i;
	}
	solve(m , n , 1 , n);
	ll res = -INF;
	for(int i = 1 ; i <= n ; i++)	res = max(res , ans[i]);
	cout << res << endl;

    return 0;
}
/*

*/

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid = l + r >> 1 , opt = -1;
      |            ~~^~~

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