Submission #573535

#	Time	Username	Problem	Language	Result	Execution time	Memory
573535		vovamr	Schools (IZhO13_school)	C++17	95 / 100	576 ms	42464 KiB

school

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct Node {
	Node *l = nullptr;
	Node *r = nullptr;
	ll p, k, s, sz;
	Node() {}
	Node(ll x) : k(x), s(x) { p = 1 + rng() % inf; sz = 1; }
}; typedef Node* node;
inline ll s(node t) { return !t ? 0 : t->s; }
inline ll sz(node t) { return !t ? 0 : t->sz; }
inline void upd(node t) { if(!t){return;} t->s = s(t->l) + t->k + s(t->r); t->sz = sz(t->l) + 1 + sz(t->r); }
inline node mg(node a, node b) {
	if (!a || !b) return (!a ? b : a);
	if (a->p > b->p) { a->r = mg(a->r, b); upd(a); return a; }
	else { b->l = mg(a, b->l); upd(b); return b; }
}
inline pair<node,node> sp(node t, int x) {
	if (!t) return {nullptr, nullptr};
	int q = sz(t->l);
	if (x > q) { auto tt = sp(t->r, x - q - 1); t->r = tt.fi; upd(t); return {t, tt.se}; }
	else { auto tt = sp(t->l, x); t->l = tt.se; upd(t); return {tt.fi, t}; }
}
inline pair<node,node> spk(node t, int x) {
	if (!t) return {nullptr, nullptr};
	if (x >= t->k) { auto tt = spk(t->r, x); t->r = tt.fi; upd(t); return {t, tt.se}; }
	else { auto tt = spk(t->l, x); t->l = tt.se; upd(t); return {tt.fi, t}; }
}
inline void pr(node t) {
	if (!t) return;
	if (t->l) pr(t->l);
	cout << t->k << " ";
	if (t->r) pr(t->r);
}

inline void insert(node &t, int x) {
	auto [t1, t2] = spk(t, x);
	t = mg(mg(t1, new Node(x)), t2);
}

inline void solve() {
	int n, A, B;
	cin >> n >> A >> B;

	ve<pii> a(n);
	for (auto &[x, y] : a) cin >> x >> y;
	sort(all(a), [](const pii &a, const pii &b) { return a.fi - a.se < b.fi - b.se; });
	reverse(all(a));

	ve<ll> sum(n, -inf);

	node t = nullptr;
	for (int i = n - 1; ~i; --i) {
		insert(t, a[i].se);

		if (n - i >= B) {
			auto [t1, t2] = sp(t, sz(t) - B);
			sum[i] = s(t2);
			t = mg(t1, t2);
		}
	}

	ll ans = 0;

	node t1 = nullptr;
	for (int i = 0; i < n - 1; ++i) {
		insert(t1, a[i].fi);

		if (i + 1 >= A) {
			auto [t2, t3] = sp(t1, sz(t1) - A);
			chmax(ans, sum[i + 1] + s(t3));
			t1 = mg(t2, t3);
		}
	}

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

• Subtask 1: 95 / 100