Advertisement
Guest User

Untitled

a guest
Dec 17th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.72 KB | None | 0 0
  1. #include <iostream>
  2. #include <ctime>
  3. #include <random>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. mt19937 rng(time(NULL));
  9.  
  10. struct node {
  11.     long long x;
  12.     long long y;
  13.  
  14.     node *l, *r;
  15.  
  16.     long long sum = 0, cnt;
  17.  
  18.     node() { }
  19.     node(int x, long long y, node *l, node *r) : x(x), y(y), l(l), r(r), sum(x), cnt(1) { }
  20. };
  21.  
  22. typedef node* treap;
  23. typedef pair<treap, treap> ptt;
  24.  
  25. long long getCnt(treap t) {
  26.     return (t ? t->cnt : 0);
  27. }
  28.  
  29. long long getSum(treap t) {
  30.     return (t ? t->sum : 0);
  31. }
  32.  
  33. treap fix(treap t) {
  34.     if (!t) {
  35.         return t;
  36.     }
  37.  
  38.     t->cnt = getCnt(t->l) + getCnt(t->r) + 1;
  39.     t->sum = getSum(t->l) + getSum(t->r) + t->x;
  40.     return t;
  41. }
  42.  
  43. ptt split(treap t, int x) {
  44.     t = fix(t);
  45.  
  46.     if (!t) {
  47.         return { t, t };
  48.     }
  49.  
  50.     if (x > t->x) {
  51.         ptt z = split(t->r, x);
  52.         t->r = z.first;
  53.         return { fix(t), z.second };
  54.     }
  55.     else {
  56.         ptt z = split(t->l, x);
  57.         t->l = z.second;
  58.         return { z.first, fix(t) };
  59.     }
  60. }
  61.  
  62. treap merge(treap a, treap b) {  //a->x < b->x
  63.     a = fix(a);
  64.     b = fix(b);
  65.  
  66.     if (!a) {
  67.         return b;
  68.     }
  69.  
  70.     if (!b) {
  71.         return a;
  72.     }
  73.  
  74.     if (a->y > b->y) {
  75.         a->r = merge(a->r, b);
  76.         return fix(a);
  77.     }
  78.     else {
  79.         b->l = merge(a, b->l);
  80.         return fix(b);
  81.     }
  82. }
  83.  
  84. treap insert(treap t, int x, long long y) {
  85.     t = fix(t);
  86.  
  87.     if (!t) {
  88.         return new node(x, y, NULL, NULL);
  89.     }
  90.  
  91.     if (y > t->y) {
  92.         ptt z = split(t, x);
  93.         return fix(new node(x, y, z.first, z.second));
  94.     }
  95.  
  96.     if (x > t->x) {
  97.         t->r = insert(t->r, x, y);
  98.     }
  99.     else {
  100.         t->l = insert(t->l, x, y);
  101.     }
  102.  
  103.     return fix(t);
  104. }
  105.  
  106. treap erase(treap t, int x)
  107. {
  108.     if (t->x == x) {
  109.         return merge(t->l, t->r);
  110.     }
  111.  
  112.     if (x > t->x) {
  113.         t->r = erase(t->r, x);
  114.     }
  115.     else {
  116.         t->l = erase(t->l, x);
  117.     }
  118.  
  119.     return fix(t);
  120. }
  121.  
  122. bool find(treap t, int x) {
  123.     if (!t) {
  124.         return false;
  125.     }
  126.  
  127.     if (t->x == x) {
  128.         return true;
  129.     }
  130.  
  131.     if (x > t->x) {
  132.         return find(t->r, x);
  133.     }
  134.  
  135.     return find(t->l, x);
  136. }
  137.  
  138. int getAns(treap t, long long cur)
  139. {
  140.     if (!t)
  141.         return -1;
  142.  
  143.     if (getSum(t->r) >= cur)
  144.         return getAns(t->r, cur);
  145.  
  146.     if (getSum(t->r) + t->x >= cur)
  147.         return getCnt(t->r) + 1;
  148.  
  149.     return getCnt(t->r) + 1 + getAns(t->l, cur - getSum(t->r) - t->x);
  150. }
  151.  
  152. #define b first
  153. #define a second
  154.  
  155. treap t = NULL;
  156. const int N = int(2 * 1e5 + 10);
  157.  
  158. pair<long long, long long> v[N];
  159.  
  160. int main() {
  161.     ios_base::sync_with_stdio(0);
  162.     cin.tie(0), cout.tie(0);
  163.  
  164.     int n;
  165.     cin >> n;
  166.  
  167.     for (int i = 0; i < n; ++i) {
  168.         cin >> v[i].a >> v[i].b;
  169.         v[i].b += v[i].a;
  170.     }
  171.  
  172.     sort(v, v + n);
  173.  
  174.     int res = -1;
  175.  
  176.     for (int i = 0; i < n; ++i)
  177.     {
  178.         t = insert(t, v[i].a, rng());
  179.  
  180.         if (getSum(t) < v[i].b)
  181.             continue;
  182.  
  183.         int ans = getAns(t, v[i].b);
  184.  
  185.         if (res == -1 || ans < res)
  186.             res = ans;
  187.     }
  188.  
  189.     cout << res << endl;
  190.  
  191.     return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement