Submission #573537

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
573537	2022-06-06T19:15:57 Z	vovamr	Schools (IZhO13_school)	C++17	100 / 100	606 ms	42600 KB

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 + 1, -inf);
	sum[n] = 0;

	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; ++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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	5 ms	876 KB	Output is correct
8	Correct	5 ms	980 KB	Output is correct
9	Correct	6 ms	980 KB	Output is correct
10	Correct	8 ms	980 KB	Output is correct
11	Correct	7 ms	1100 KB	Output is correct
12	Correct	6 ms	972 KB	Output is correct
13	Correct	48 ms	5444 KB	Output is correct
14	Correct	123 ms	11368 KB	Output is correct
15	Correct	341 ms	22868 KB	Output is correct
16	Correct	320 ms	25916 KB	Output is correct
17	Correct	403 ms	31276 KB	Output is correct
18	Correct	438 ms	34392 KB	Output is correct
19	Correct	488 ms	37052 KB	Output is correct
20	Correct	606 ms	42600 KB	Output is correct