Advertisement
Guest User

Untitled

a guest
Aug 30th, 2016
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. inline int readChar();
  6. template <class T = long long> inline T readInt();
  7. template <class T> inline void writeInt( T x, char end = 0 );
  8. inline void writeChar( int x );
  9. inline void writeWord( const char *s );
  10.  
  11. /** Read */
  12.  
  13. static const int buf_size = 4096;
  14.  
  15. inline int getChar() {
  16.     static char buf[buf_size];
  17.     static int len = 0, pos = 0;
  18.     if (pos == len)
  19.         pos = 0, len = fread(buf, 1, buf_size, stdin);
  20.     if (pos == len)
  21.         return -1;
  22.     return buf[pos++];
  23. }
  24.  
  25. inline int readChar() {
  26.     int c = getChar();
  27.     while (c <= 32)
  28.         c = getChar();
  29.     return c;
  30. }
  31.  
  32. template <class T>
  33. inline T readInt() {
  34.     int s = 1, c = readChar();
  35.     T x = 0;
  36.     if (c == '-')
  37.         s = -1, c = getChar();
  38.     while ('0' <= c && c <= '9')
  39.         x = x * 10 + c - '0', c = getChar();
  40.     return s == 1 ? x : -x;
  41. }
  42.  
  43.  
  44. const int MAX_MEM = 1e7 * 3;
  45. int mpos = 0;
  46. char mem[MAX_MEM];
  47. inline void * operator new ( size_t n ) {
  48.     char *res = mem + mpos;
  49.     mpos += n;
  50.     assert(mpos <= MAX_MEM);
  51.     return (void *)res;
  52. }
  53. inline void operator delete ( void * ) { } // обязательно!
  54. //inline void * operator new [] ( size_t ) { assert(0); }
  55. //inline void operator delete [] ( void * ) { assert(0); }
  56.  
  57. int r = 1;
  58.  
  59. int rnd()
  60. {
  61.     r = (r + 1791791) % (int)(1e9 + 7);
  62.     return r;
  63. }
  64.  
  65. struct treap
  66. {
  67.     int y, price;
  68.     long long num;
  69.     long long a_num, profit;
  70.     treap *l, *r;
  71.     treap(int a, int b)
  72.     {
  73.         y = rnd();
  74.         price = a;
  75.         num = b;
  76.         a_num = num;
  77.         profit = price * num;
  78.         l = 0;
  79.         r = 0;
  80.     }
  81. };
  82.  
  83. long long get_anum(treap *t)
  84. {
  85.     if (!t)
  86.         return 0;
  87.     return t->a_num;
  88. }
  89.  
  90. long long get_pr(treap *t)
  91. {
  92.     if (!t)
  93.         return 0;
  94.     return t->profit;
  95. }
  96.  
  97. void recalc(treap *t)
  98. {
  99.     if (t != 0)
  100.     {
  101.         t->a_num = get_anum(t->l) + t->num + get_anum(t->r);
  102.         t->profit = get_pr(t->l) + t->num * t->price + get_pr(t->r);
  103.     }
  104. }
  105.  
  106. treap* merge(treap *a, treap *b)
  107. {
  108.     if (!a)
  109.         return b;
  110.     if (!b)
  111.         return a;
  112.     treap *res;
  113.     if (a->y > b->y)
  114.     {
  115.         a->r = merge(a->r, b);
  116.         res = a;
  117.     }
  118.     else
  119.     {
  120.         b->l = merge(a, b->l);
  121.         res = b;
  122.     }
  123.     recalc(res);
  124.     return res;
  125. }
  126.  
  127. treap** split(treap *a, long long k)
  128. {
  129.     if (!a)
  130.         return new treap*[2] {0, 0};
  131.     treap **res;
  132.     if (a->price > k)
  133.     {
  134.         res = split(a->l, k);
  135.         a->l = res[1];
  136.         res[1] = a;
  137.         recalc(res[1]);
  138.     }
  139.     else
  140.     {
  141.         res = split(a->r, k);
  142.         a->r = res[0];
  143.         res[0] = a;
  144.         recalc(res[0]);
  145.     }
  146.     return res;
  147. }
  148.  
  149. struct my
  150. {
  151.     long long place;
  152.     long long num, price;
  153. };
  154.  
  155. int main() {
  156.     long long n = readInt(), m=readInt(), p = readInt();
  157.     pair<long long, long long> fish[n];
  158.     my shop[m];
  159.     for (int i = 0; i < n; i++)
  160.         fish[i].first = readInt(), fish[i].second = readInt();
  161.     for (int i = 0; i < m; i++)
  162.         shop[i].place = readInt(), shop[i].num=readInt(), shop[i].price = readInt();
  163.         //cin >> shop[i].place >> shop[i].num >> shop[i].price;
  164.     treap *root = 0;
  165.     int i = 0, j = 0;
  166.     long long caught = 0;
  167.     long long res = 0;
  168.     while (i < n || j < m)
  169.     {
  170.         long long place;
  171.         if (j == m || (i < n && fish[i].first < shop[j].place))
  172.         {
  173.             place = fish[i].first;
  174.             caught += fish[i].second;
  175.             i++;
  176.         }
  177.         else
  178.         {
  179.             auto ins = new treap(shop[j].price, shop[j].num);
  180.             place = shop[j].place;
  181.             j++;
  182.             auto t1 = split(root, ins->price);
  183.             t1[0] = merge(t1[0], ins);
  184.             root = merge(t1[0], t1[1]);
  185.         }
  186.         long long to_sell = caught;
  187.         long long curr = -place * p;
  188.         auto our = root;
  189.         while (our && to_sell > 0)
  190.         {
  191.             if (our->a_num <= to_sell)
  192.             {
  193.                 curr += our->profit;
  194.                 to_sell = 0;
  195.             }
  196.             else if (get_anum(our->r) >= to_sell)
  197.                 our = our->r;
  198.             else
  199.             {
  200.                 to_sell -= get_anum(our->r);
  201.                 curr += get_pr(our->r);
  202.                 curr += min(to_sell, (long long)our->num) * our->price;
  203.                 to_sell -= min(to_sell, (long long)our->num);
  204.                 if (to_sell > 0)
  205.                     our = our->l;
  206.             }
  207.         }
  208.         res = max(res, curr);
  209.     }
  210.     cout << res;
  211. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement