Submission #135679

#	Time	Username	Problem	Language	Result	Execution time	Memory
135679		E869120	Cake 3 (JOI19_cake3)	C++14	100 / 100	3480 ms	35380 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

class SegmentTree {
public:
	vector<long long> dat1, dat2; int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat1.resize(size_ * 2, 0);
		dat2.resize(size_ * 2, 0);
	}
	void add(int pos,long long x) {
		pos += size_;
		while (pos >= 1) {
			dat1[pos]++; dat2[pos] += x;
			pos >>= 1;
		}
	}
	void lose(int pos, long long x) {
		pos += size_;
		while (pos >= 1) {
			dat1[pos]--; dat2[pos] -= x;
			pos >>= 1;
		}
	}
	long long getmax(long long M) {
		int u = 1; long long cx = 0;
		while (u < size_) {
			if (dat1[u * 2 + 1] <= M) {
				M -= dat1[u * 2 + 1];
				cx += dat2[u * 2 + 1];
				u = u * 2;
			}
			else {
				u = u * 2 + 1;
			}
		}
		if (M > 0) {
			M -= dat1[u];
			cx += dat2[u];
			if (M > 0) return -(1LL << 60);
		}
		return cx;
	}
};

long long N, M, C[1 << 18], V[1 << 18], ans[1 << 18], id[1 << 18], SIZE_ = 1;
vector<pair<long long, long long>>A, B;

int main() {
	// --------------------------- 入力・ソート ----------------------
	scanf("%lld%lld", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%lld%lld", &V[i], &C[i]);
		A.push_back(make_pair(C[i], V[i]));
	}
	sort(A.begin(), A.end());
	for (int i = 1; i <= N; i++) {
		C[i] = A[i - 1].first; V[i] = A[i - 1].second;
		B.push_back(make_pair(V[i], i));
	}
	sort(B.begin(), B.end());

	// ---------------------------- ただの分割 -----------------------
	while (SIZE_ <= N) SIZE_ *= 2;
	ans[SIZE_] = -(1LL << 60); id[SIZE_] = N;
	ans[0] = -(1LL << 60); id[0] = 1;

	for (int i = (SIZE_ >> 1); i >= 1; i >>= 1) {
		vector<int> vec;
		for (int j = i; j < SIZE_; j += i * 2) vec.push_back(j);

		SegmentTree Z; Z.init(SIZE_ + 1);

		int cx = N + 1;
		for (int j = vec.size() - 1; j >= 0; j--) {
			// 新たに追加する
			for (int k = vec[j]; k < min((int)id[vec[j] + i] + 1, cx); k++) {
				if (k <= N) {
					int pos1 = lower_bound(B.begin(), B.end(), make_pair(V[k], 1LL * k)) - B.begin();
					Z.add(pos1, V[k]);
				}
			}

			// 答えを求める
			pair<long long, int> maxid = make_pair(-(1LL << 59), N);
			for (int k = id[vec[j] + i]; k >= id[vec[j] - i]; k--) {
				long long v = Z.getmax(M) - 2LL * (C[k] - C[vec[j]]);
				maxid = max(maxid, make_pair(v, k));
				if (k >= vec[j] && k != id[vec[j] - i]) {
					int pos1 = lower_bound(B.begin(), B.end(), make_pair(V[k], 1LL * k)) - B.begin();
					Z.lose(pos1, V[k]);
				}
			}
			ans[vec[j]] = maxid.first;
			id[vec[j]] = maxid.second;

			cx = vec[j];
		}
	}

	// --------------------------- 答えを求める ----------------------
	long long FinalAns = -(1LL << 60);
	for (int i = 1; i <= N; i++) FinalAns = max(FinalAns, ans[i]);
	cout << FinalAns << endl;
	return 0;
}

Compilation message (stderr)

cake3.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
cake3.cpp: In function 'int main()':
cake3.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &V[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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