Guest User

Untitled

a guest
Dec 18th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstdio>
  5.  
  6. #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
  7.  
  8. using namespace std;
  9.  
  10. typedef long long int64;
  11.  
  12. const double eps = 1e-9;
  13.  
  14. struct item{
  15.     int q, index;
  16.     int64 sum;
  17.     item *l, *r;
  18.     item(){}
  19. };
  20.  
  21. typedef item* pnode;
  22.  
  23. bool cm = 0;
  24.  
  25. item _[1000001];
  26. int64 ln = 0;
  27.  
  28. pnode node(int64 q, int64 index){
  29.     pnode res = &_[ln++];
  30.     res->q = q, res->index = index, res->sum = q;
  31.     res->l = res->r = 0;
  32.     return res;
  33. }
  34.  
  35. #define sum(x) ((x) ? ((x)->sum) : 0)
  36. #define upd_sum(x) ((x)->sum = sum((x)->l) + sum((x)->r) + (x)->q)
  37.  
  38. static int cc = 0;
  39.  
  40. pnode merge(pnode l, pnode r){
  41.     if (!l || !r)
  42.         return l ? l : r;
  43.     if (l->q < r->q)
  44.         swap(l, r);
  45.     if (cc ^= 1)
  46.         swap(l->l, l->r);
  47.     l->r = merge(l->r, r);
  48.     upd_sum(l);
  49.     return l;
  50. }
  51.  
  52. const int cmax = 500001;
  53.  
  54. int n;
  55. int s[cmax], q[cmax];
  56. double sq[cmax];
  57. int64 w;
  58. int p[cmax];
  59.  
  60. inline bool cmp(int a, int b){
  61.     return sq[a] < sq[b];
  62. }
  63.  
  64. pnode rt = 0;
  65.  
  66. void print(pnode a, vector<int> &ans){
  67.     if (!a)
  68.         return;
  69.     print(a->l, ans);
  70.     ans.push_back(a->index + 1);
  71.     print(a->r, ans);
  72. }
  73.  
  74. int dl[cmax], len = 0;
  75. pnode where[cmax];
  76. vector<int> res;
  77. int sz = 0;
  78.  
  79. #define init(x) ((x)->l = (x)->r = 0, (x)->sum = (x)->q)
  80.  
  81. int main(){
  82.     #ifdef CUTEBMAING
  83.     freopen("input.txt", "r", stdin);
  84.     freopen("output.txt", "w", stdout);
  85.     #endif
  86.     scanf("%d %lld", &n, &w);
  87.     for (int i = 0; i < n; i++)
  88.         scanf("%d %d", &s[i], &q[i]), sq[i] = 1.0 * s[i] / q[i];
  89.     for (int i = 0; i < n; i++)
  90.         p[i] = i;
  91.     sort(p, p + n, cmp);
  92.     int64 ans = 0, wh = 0;
  93.     double cost = 0;
  94.     for (int i = 0; i < n; i++)
  95.         where[i] = node(q[i], i);
  96.     for (int i = 0; i < n; i++){
  97.         len = 0;
  98.         dl[len++] = p[i];
  99.         while (rt && 1.0 * sum(rt) * sq[p[i]] + eps > w)
  100.             rt = merge(rt->l, rt->r), --sz;
  101.         while (rt && 1.0 * sum(rt) * sq[p[i]] + s[p[i]] + eps > w){
  102.             dl[len++] = rt->index;
  103.             rt = merge(rt->l, rt->r), --sz;
  104.         }
  105.         double ccost = 1.0 * sum(rt) * sq[p[i]] + s[p[i]];
  106.         if (ccost - eps < w && (ans < sz + 1 || (ans == sz + 1 && cost > ccost)))
  107.             ans = sz + 1, wh = i, cost = ccost;
  108.         for (int i = 0; i < len; i++)
  109.             init(where[dl[i]]), rt = merge(rt, where[dl[i]]), ++sz;
  110.     }
  111.     rt = 0;
  112.     for (int i = 0; i < wh; i++)
  113.         init(where[p[i]]), rt = merge(rt, where[p[i]]);
  114.     while (rt && 1.0 * sum(rt) * sq[p[wh]] + s[p[wh]] - eps > w)
  115.         rt = merge(rt->l, rt->r);
  116.     printf("%lld\n", ans);
  117.     print(rt, res);
  118.     if (ans > 0)
  119.         res.push_back(p[wh] + 1);
  120.     sort(res.begin(), res.end());
  121.     foreach(i, res)
  122.         printf("%d\n", *i);
  123.     return 0;
  124. }
Add Comment
Please, Sign In to add comment