Submission #872801

#	Time	Username	Problem	Language	Result	Execution time	Memory
872801		mat_jur	Cake 3 (JOI19_cake3)	C++17	0 / 100	0 ms	348 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

struct segtree {
	int base;
	vector<int> tree;
	segtree(int n) {
		base = 1;
		while (base < n) base *= 2;
		tree.resize(2*base, -1);
	}
	void update(int v, int x) {
		v += base;
		tree[v] = x;
		v /= 2;
		while(v>0) {
			tree[v] = max(tree[2*v],tree[2*v+1]);
			v /= 2;
		}
	}
	int query(int a, int b) {
		a += base-1; b += base+1;
		int res = -1;
		while (a/2 != b/2) {
			if (a%2==0) res = max(res, tree[a+1]);
			if (b%2==1) res = max(res, tree[b-1]);
			a /= 2; b /= 2;
		}
		return res;
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> t(n);
	for (auto &[v, c] : t) cin >> v >> c;
	auto comp = [&](pair<int, int> a, pair<int, int> b) {
		return mp(a.se, a.fi) < mp(b.se, b.fi);
	};
	sort(all(t));
	debug(t);
	ll sumv = 0;
	REP(i, m) sumv += t[i].fi;
	segtree maxx(n), minn(n);
	REP(i, n) {maxx.update(i, t[i].se); minn.update(i, -t[i].se);}
	ll res = sumv-2*(maxx.query(0, m-1)+minn.query(0, m-1));
	FOR(i, 1, n-m) {
		sumv -= t[i-1].fi;
		sumv += t[i+m-1].fi;
		res = max(res, sumv-2*(maxx.query(i, i+m-1)+minn.query(i, i+m-1)));
	}
	cout << res;

	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:58:7: warning: variable 'comp' set but not used [-Wunused-but-set-variable]
   58 |  auto comp = [&](pair<int, int> a, pair<int, int> b) {
      |       ^~~~

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