Submission #376823

#	Time	Username	Problem	Language	Result	Execution time	Memory
376823		casperwang	Cake 3 (JOI19_cake3)	C++14	100 / 100	2970 ms	26172 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define tiiii tuple<int,int,int,int>
#define pb emplace_back
#define All(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 200000;
const int INF = 1e18;
int N, M;
int ans = -INF;
struct Node {
	int c, v, vid;
} arr[MAXN+1];

class Seg {
	private:
		int cnt[MAXN*4+5];
		int sum[MAXN*4+5];
		void pull(int now) {
			cnt[now] = cnt[now*2] + cnt[now*2+1];
			sum[now] = sum[now*2] * (cnt[now*2] > 0) + sum[now*2+1] * (cnt[now*2+1] > 0);
		}
	public:
		void build(int now=1, int l=1, int r=N) {
			if (l == r) {
				sum[now] = arr[l].v;
				cnt[now] = 0;
				return;
			}
			int mid = l + r >> 1;
			build(now*2  , l, mid);
			build(now*2+1,mid+1,r);
			pull(now);
		}
		void mdy(int p, int k, int now=1, int l=1, int r=N) {
			if (l == p && r == p) {
				cnt[now] += k;
				return;
			} else if (l > p || r < p) return;
			int mid = l + r >> 1;
			mdy(p, k, now*2  , l, mid);
			mdy(p, k, now*2+1,mid+1,r);
			pull(now);
		}
		int qry(int k, int now=1, int l=1, int r=N) {
			if (k == cnt[now]) {
				return sum[now];
			}
			int mid = l + r >> 1, s = 0;
			s += qry(min(cnt[now*2], k), now*2, l, mid);
			if (cnt[now*2] < k)
				s += qry(k - cnt[now*2], now*2+1, mid+1, r);
			return s;
		}
} seg;

void solve(vector<tiiii> qry) {
	vector <tiiii> nxt;
	int nowL = 1, nowR = 0;
	for (auto [L, R, l, r] : qry) {
		int mid = L + R >> 1;
		int K = arr[mid].v + 2 * arr[mid].c;
		pii mmax(-INF, -1);
		while (nowR+1 < l) {
			nowR++;
			seg.mdy(arr[nowR].vid, 1);
		}
		while (nowL <= mid) {
			seg.mdy(arr[nowL].vid, -1);
			nowL++;
		}
		if (nowR - nowL + 1 >= M-2) {
			//debug(nowR+1, K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c);
			mmax = max(mmax, pii(K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c, nowR+1));
		}
		while (nowR+1 < r) {
			nowR++;
			seg.mdy(arr[nowR].vid, 1);
			if (nowR - nowL + 1 >= M-2) {
				//debug(nowR+1, K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c);
				mmax = max(mmax, pii(K + seg.qry(M-2) + arr[nowR+1].v - 2 * arr[nowR+1].c, nowR+1));
			}
		}
		ans = max(ans, mmax.ff);
		if (mid > L)
			nxt.pb(L, mid-1, l, mmax.ss);
		if (R > mid)
			nxt.pb(mid+1, R, mmax.ss, r);
	}
	while (nowL <= nowR)
		seg.mdy(arr[nowL++].vid, -1);
	if (nxt.size())
		solve(nxt);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i].v >> arr[i].c;
	}
	sort(arr+1, arr+1+N, [](const Node a, const Node b) {
		return a.v > b.v;
	});
	for (int i = 1; i <= N; i++) {
		arr[i].vid = i;
	}
	seg.build();
	sort(arr+1, arr+1+N, [](const Node a, const Node b) {
		return a.c < b.c;
	});
	vector <tiiii> I;
	I.pb(1, N-M+1, M, N);
	solve(I);
	cout << ans << '\n';
}

Compilation message (stderr)

cake3.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
cake3.cpp:38:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    int mid = l + r >> 1;
      |              ~~^~~
cake3.cpp: In member function 'void Seg::mdy(long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |    int mid = l + r >> 1;
      |              ~~^~~
cake3.cpp: In member function 'long long int Seg::qry(long long int, long long int, long long int, long long int)':
cake3.cpp:57:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |    int mid = l + r >> 1, s = 0;
      |              ~~^~~
cake3.cpp: In function 'void solve(std::vector<std::tuple<long long int, long long int, long long int, long long int> >)':
cake3.cpp:68:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |  for (auto [L, R, l, r] : qry) {
      |            ^
cake3.cpp:69:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int mid = L + R >> 1;
      |             ~~^~~

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