Submission #197541

#	Time	Username	Problem	Language	Result	Execution time	Memory
197541		Juney	Cake 3 (JOI19_cake3)	C++14	0 / 100	2 ms	376 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5 + 5;
 
ll N, M, ans;
pii A[MAXN];
 
ll comp[MAXN], root[MAXN];
int get_idx(ll val) { return lower_bound(comp+1, comp+1+N, val) - comp; }
 
struct PST {
	struct NODE { ll l, r, cnt, sum; } T[MAXN * 30];
	int sz;
	int make(int v, int l, int r, int n) {
		if(r < v || v < l) return n;
		int cur = ++sz;
		T[cur] = T[n];
		if(l != r) {
			int mid = l + r >> 1;
			T[cur].l = make(v, l, mid, T[n].l);
			T[cur].r = make(v, mid+1, r, T[n].r);
		}
		T[cur].cnt++;
		T[cur].sum += comp[v];
		return cur;
	}
	ll query(int tot, int l, int r, int n1, int n2) {
		if(l == r) {
			int cnt = M - tot;
			return comp[l] * cnt;
		}
		int cnt = T[T[n2].r].cnt - T[T[n1].r].cnt;
		ll sum = T[T[n2].r].sum - T[T[n1].r].sum;
		int mid = l + r >> 1;
		if(tot + cnt >= M) return query(tot, mid+1, r, T[n1].r, T[n2].r);
		else return sum + query(tot + cnt, l, mid, T[n1].l, T[n2].l);
	}
} pst;
 
void f(int s, int e, int l, int r) {
	if(l > r || s > e) return;
	int mid = l + r >> 1;
	ll k, MAX = -1e18;
	for(int i=max(s, mid); i<=e; i++) {
		ll q = pst.query(0, 1, N, root[mid-1], root[i]) - 2 * (A[i].fi - A[mid].fi);
		if(MAX < q) {
			MAX = q;
			k = i;
		}
	}
	ans = max(ans, MAX);
	f(s, k, l, mid-1); f(k, e, mid+1, r);
}
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for(int i=1; i<=N; i++) {
		cin >> A[i].se >> A[i].fi;
		comp[i] = A[i].se;
	}
	sort(comp+1, comp+1+N);
	sort(A+1, A+1+N);
	for(int i=1; i<=N; i++) root[i] = pst.make(get_idx(A[i].se), 1, N, root[i-1]); 
	f(1, N, 1, N);
	cout << ans;
}

Compilation message (stderr)

cake3.cpp: In member function 'int PST::make(int, int, int, int)':
cake3.cpp:27:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l + r >> 1;
              ~~^~~
cake3.cpp: In member function 'll PST::query(int, int, int, int, int)':
cake3.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
cake3.cpp: In function 'void f(int, int, int, int)':
cake3.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
cake3.cpp:60:3: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  f(s, k, l, mid-1); f(k, e, mid+1, r);
  ~^~~~~~~~~~~~~~~~

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