Submission #573534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
573534	2022-06-06T19:07:48 Z	vovamr	Schools (IZhO13_school)	C++17	95 / 100	552 ms	43416 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(t1, mg(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);
		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);
		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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	5 ms	928 KB	Output is correct
8	Correct	5 ms	980 KB	Output is correct
9	Correct	5 ms	956 KB	Output is correct
10	Correct	6 ms	972 KB	Output is correct
11	Correct	6 ms	980 KB	Output is correct
12	Correct	6 ms	1020 KB	Output is correct
13	Correct	49 ms	5712 KB	Output is correct
14	Correct	126 ms	12192 KB	Output is correct
15	Correct	281 ms	23448 KB	Output is correct
16	Correct	328 ms	26480 KB	Output is correct
17	Correct	377 ms	31996 KB	Output is correct
18	Correct	424 ms	35036 KB	Output is correct
19	Correct	457 ms	37668 KB	Output is correct
20	Correct	552 ms	43416 KB	Output is correct