Submission #411477

#	Time	Username	Problem	Language	Result	Execution time	Memory
411477		amoo_safar	Cake 3 (JOI19_cake3)	C++17	100 / 100	711 ms	16624 KiB

cake3

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

vector<pll> A, V;
ll ans = -Inf;
int ridx[N];
int n, m;

struct Fenwick {
	ll fen[N];
	Fenwick (){
		memset(fen, 0, sizeof fen);
	}
	void Add(int idx, ll x){
		// cerr << "^^ " << idx << ' ' << x << '\n';
		idx += 2;
		for(; idx < N; idx += (idx & (-idx)))
			fen[idx] += x;
	}
	ll Get(int idx){
		idx += 2;
		ll res = 0;
		for(; idx; idx -= (idx & (-idx)))
			res += fen[idx];
		return res;
	}
	ll GetK(int k){
		int nw = 0;
		for(int i = Log - 1; i >= 0; i--){
			int st = (1 << i);
			if(nw + st >= N) continue;
			if(fen[nw + st] <= k){
				nw += st;
				k -= fen[nw];
			}
		}
		return nw - 2;
	}
};
Fenwick On, Sum;

void Add(int id, int del){
	// cerr << "# " << id << ' ' << del << '\n';
	int pos = ridx[id];
	On.Add(pos, del);
	Sum.Add(pos, A[id].S * del);
}
int L = 1, R = 0; // []
ll Get(int lq, int rq){
	if(rq - lq + 1 < m) return -Inf;

	while(R < rq) Add(++R, 1);
	while(L > lq) Add(--L, 1);

	while(R > rq) Add(R--, -1);
	while(L < lq) Add(L++, -1);

	// cerr << '\n';
	// debug(On.GetK(m));
	// for(int i = 0; i < 7; i++) cerr << On.Get(i) - On.Get(i - 1) << ' ';
	// cerr << '\n';
	return Sum.Get(On.GetK(m)) - 2ll * (A[rq].F - A[lq].F);
}

void Solve(int l, int r, int lo, int ro){
	if(r - l < 1) return ;
	ll mx = -Inf, opt = lo;
	int mid = (l + r) >> 1;
	ll res;
	for(int i = lo; i <= ro; i++){
		if(i > mid) break;
		res = Get(i, mid);
		if(res > mx){
			mx = res;
			opt = i;
		}
	}
	ans = max(ans, mx);

	Solve(l, mid, lo, opt + 1);
	Solve(mid + 1, r, opt, ro);
}
// naive
int OPT[N];
void NAIVE(){
	for(int i = 0; i < n; i++){
		ll res;
		ll mx = -Inf;
		for(int j = 0; j < n; j++){
			if(j > i) break;
			res = Get(j, i);
			if(res > mx){
				mx = res;
				OPT[i] = j;
			}
		}
		ans = max(ans, mx);	
	}
	for(int i = 1; i < n; i++)
		assert(OPT[i - 1] <= OPT[i]);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	ll val, cost;
	for(int i = 0; i < n; i++){
		cin >> val >> cost;
		A.pb({cost, val});
	}
	sort(all(A));
	for(int i = 0; i < n; i++)
		V.pb({A[i].S, i});
	sort(all(V)); reverse(all(V));
	for(int i = 0; i < n; i++)
		ridx[V[i].S] = i;

	Solve(0, n, 0, n);
	// NAIVE();
	// debug(Get(0, 4));
	cout << ans << '\n';
	// debug(Sum.Get(N - 5));
	// debug(Sum.Get(78));
	return 0;
}

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