Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <ctime>
- #include <random>
- #include <algorithm>
- using namespace std;
- mt19937 rng(time(NULL));
- struct node {
- long long x;
- long long y;
- node *l, *r;
- long long sum = 0, cnt;
- node() { }
- node(int x, long long y, node *l, node *r) : x(x), y(y), l(l), r(r), sum(x), cnt(1) { }
- };
- typedef node* treap;
- typedef pair<treap, treap> ptt;
- long long getCnt(treap t) {
- return (t ? t->cnt : 0);
- }
- long long getSum(treap t) {
- return (t ? t->sum : 0);
- }
- treap fix(treap t) {
- if (!t) {
- return t;
- }
- t->cnt = getCnt(t->l) + getCnt(t->r) + 1;
- t->sum = getSum(t->l) + getSum(t->r) + t->x;
- return t;
- }
- ptt split(treap t, int x) {
- t = fix(t);
- if (!t) {
- return { t, t };
- }
- if (x > t->x) {
- ptt z = split(t->r, x);
- t->r = z.first;
- return { fix(t), z.second };
- }
- else {
- ptt z = split(t->l, x);
- t->l = z.second;
- return { z.first, fix(t) };
- }
- }
- treap merge(treap a, treap b) { //a->x < b->x
- a = fix(a);
- b = fix(b);
- if (!a) {
- return b;
- }
- if (!b) {
- return a;
- }
- if (a->y > b->y) {
- a->r = merge(a->r, b);
- return fix(a);
- }
- else {
- b->l = merge(a, b->l);
- return fix(b);
- }
- }
- treap insert(treap t, int x, long long y) {
- t = fix(t);
- if (!t) {
- return new node(x, y, NULL, NULL);
- }
- if (y > t->y) {
- ptt z = split(t, x);
- return fix(new node(x, y, z.first, z.second));
- }
- if (x > t->x) {
- t->r = insert(t->r, x, y);
- }
- else {
- t->l = insert(t->l, x, y);
- }
- return fix(t);
- }
- treap erase(treap t, int x)
- {
- if (t->x == x) {
- return merge(t->l, t->r);
- }
- if (x > t->x) {
- t->r = erase(t->r, x);
- }
- else {
- t->l = erase(t->l, x);
- }
- return fix(t);
- }
- bool find(treap t, int x) {
- if (!t) {
- return false;
- }
- if (t->x == x) {
- return true;
- }
- if (x > t->x) {
- return find(t->r, x);
- }
- return find(t->l, x);
- }
- int getAns(treap t, long long cur)
- {
- if (!t)
- return -1;
- if (getSum(t->r) >= cur)
- return getAns(t->r, cur);
- if (getSum(t->r) + t->x >= cur)
- return getCnt(t->r) + 1;
- return getCnt(t->r) + 1 + getAns(t->l, cur - getSum(t->r) - t->x);
- }
- #define b first
- #define a second
- treap t = NULL;
- const int N = int(2 * 1e5 + 10);
- pair<long long, long long> v[N];
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> v[i].a >> v[i].b;
- v[i].b += v[i].a;
- }
- sort(v, v + n);
- int res = -1;
- for (int i = 0; i < n; ++i)
- {
- t = insert(t, v[i].a, rng());
- if (getSum(t) < v[i].b)
- continue;
- int ans = getAns(t, v[i].b);
- if (res == -1 || ans < res)
- res = ans;
- }
- cout << res << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement