제출 #541814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541814		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++17	0 / 100	6 ms	6852 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll,int>
#define f first
#define s second
#define endl "\n"
 
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, n, val[N], a[N], cur = 0, ch1[2 * N], ch2[2 * N];
pii p[N];
ll ans;
struct node{
	int cn;
	ll sum;
} tree[4 * N];
int m;
void add(int u, int l, int r, int id, int t) {
	if(l > id || r < id) return;
	if(l == r) {
		tree[u].cn += t;
		tree[u].sum += t * val[id];
		return;
	}
	int mid = (l + r) >> 1;
	if(id <= mid) add(ch1[u], l, mid, id, t); 
	else add(ch2[u], mid + 1, r, id, t);
	tree[u].cn = tree[ch1[u]].cn + tree[ch2[u]].cn;
	tree[u].sum = tree[ch1[u]].sum + tree[ch2[u]].sum;
}
void add(int id, int t) {
	add(1, 1, cur, id, t);
}
ll get(int u,int l,int r,int k) {
	if(!k) return 0;
	if(l == r) {
		return (ll)min(tree[u].cn, k) * val[l];
	}
	int mid = (l + r) >> 1;
	if(tree[ch2[u]].cn <= k) return tree[ch2[u]].sum + get(ch1[u], l, mid, k - tree[ch2[u]].cn);
	return get(ch2[u], mid + 1, r, k);
}
void solve(int l,int r,int ql, int qr) {
	if(r < l || ql > qr) return;
	int mid = (l + r) >> 1;
	pii opt; opt = {-2e17, ql};
	for(int i = mid; i >= max(l, qr + 1); i--) add(a[i], 1);
	if(mid < max(l, qr + 1))add(a[mid], 1);
	for(int i = min(qr, mid - 1);  i >= ql; i--) {
		add(a[i], 1); 
		if(mid - i + 1 >= m) 
		opt = max(opt, make_pair(get(1, 1, cur, m) - 2 * (p[mid].f - p[i].f), i));
	}
	ans = max(ans, opt.f);

	if(mid < max(l, qr + 1))add(a[mid], -1);
	for(int i = mid; i >= max(l, qr + 1); i--) add(a[i], -1);
	for(int i = min(qr, mid - 1);  i >= ql; i--) add(a[i], -1);
	if(l == r) return;
	for(int i = opt.s + 1; i <= min(qr, l - 1); i++) add(a[i], 1);
	solve(l, mid - 1, ql, opt.s); 
	for(int i = opt.s + 1; i <= min(qr, l - 1); i++) add(a[i], -1);
	for(int i = max(l, qr + 1); i <= mid; i++) add(a[i], 1);
	solve(mid + 1,r, opt.s, qr);
	for(int i = max(l, qr + 1); i <= mid; i++) add(a[i], -1);
	
}
main() {
	ios_base::sync_with_stdio(false),
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	ans = -1e18;
	vector<pair<int,int> > x;
	for(int i = 1; i <= 2 * N; i++) ch1[i] = 2 * i, ch2[i] = ch1[i] + 1;
	for(int i = 1; i <= n; i++) {
		cin >> p[i].s >> p[i].f;
	}
	sort(p + 1, p + n + 1);
	for(int i = 1; i <= n; i++) {
		x.push_back({p[i].s, i});
	}
	sort(x.begin(), x.end());
	for(int i = 0; i < x.size(); i++) {
		if(!i || x[i].f != x[i - 1].f) cur++;
		val[cur] = x[i].f;
		a[x[i].s] = cur;
	}
	solve(1, n, 1, n);
	cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
cake3.cpp:75:41: warning: iteration 400009 invokes undefined behavior [-Waggressive-loop-optimizations]
   75 |  for(int i = 1; i <= 2 * N; i++) ch1[i] = 2 * i, ch2[i] = ch1[i] + 1;
      |                                  ~~~~~~~^~~~~~~
cake3.cpp:75:19: note: within this loop
   75 |  for(int i = 1; i <= 2 * N; i++) ch1[i] = 2 * i, ch2[i] = ch1[i] + 1;
      |                 ~~^~~~~~~~

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