Advertisement
Guest User

Untitled

a guest
Oct 28th, 2016
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int maxn = 1e5 + 100, inf = 1e9 + 100, mod = 1e9 + 993;
  8.  
  9. int n;
  10.  
  11. pair<int, int> q[4 * maxn];
  12.  
  13. void upd(int v, int l, int r){
  14. if (q[v].second == 0)
  15. return;
  16. q[v].first += q[v].second;
  17. int m = (l + r) / 2;
  18. if (l != m)
  19. q[2 * v].second += q[v].second;
  20. if (r != m)
  21. q[2 * v + 1].second += q[v].second;
  22. q[v].second = 0;
  23. }
  24.  
  25. void update(int v, int tl, int tr, int l, int r, int val){
  26. upd(v, tl, tr);
  27. if (l > r)
  28. return;
  29. if (tl == l && tr == r){
  30. q[v].second += val;
  31. upd(v, tl, tr);
  32. return;
  33. }
  34. int m = (tl + tr) / 2;
  35. update(2 * v, tl, m, l, min(r, m), val);
  36. update(2 * v + 1, m + 1, tr, max(l, m + 1), r, val);
  37. q[v].first = min(q[2 * v].first, q[2 * v + 1].first);
  38. }
  39.  
  40. ll sum(int v, int tl, int tr, int l, int r){
  41. upd(v, tl, tr);
  42. if (l > r)
  43. return inf;
  44. if (tl == l && tr == r)
  45. return q[v].first;
  46. int m = (tl + tr) / 2;
  47. return min(sum(2 * v, tl, m, l, min(r, m)), sum(2 * v + 1, m + 1, tr, max(l, m + 1), r));
  48. }
  49.  
  50. struct treap{
  51. ll v, uv, m, d, y;
  52. treap *l, *r;
  53. };
  54.  
  55. typedef treap * ptr;
  56.  
  57. ptr create(int v, int m, int d){
  58. ptr t = new treap;
  59. t->v = v;
  60. t->uv = -1;
  61. t->m = m;
  62. t->d = d;
  63. t->l = nullptr;
  64. t->r = nullptr;
  65. t->y = rand();
  66. return t;
  67. }
  68.  
  69. void upd(ptr &t){
  70. if (t == nullptr)
  71. return;
  72. if (t->uv != -1){
  73. t->v += t->uv;
  74. if (t->l != nullptr)
  75. if (t->l->uv == -1)
  76. t->l->uv = t->uv;
  77. else
  78. t->l->uv += t->uv;
  79. if (t->r != nullptr)
  80. if (t->r->uv == -1)
  81. t->r->uv = t->uv;
  82. else
  83. t->r->uv += t->uv;
  84. t->uv = -1;
  85. }
  86. }
  87.  
  88. void split(ptr t, ptr &l, ptr &r, int v, int d){
  89. if (t == nullptr){
  90. l = nullptr;
  91. r = nullptr;
  92. return;
  93. }
  94. upd(t);
  95. if (t->v < v || (t->v == v && t->d <= d))
  96. split(t->r, t->r, r, v, d), l = t;
  97. else
  98. split(t->l, l, t->l, v, d), r = t;
  99. upd(l);
  100. upd(r);
  101. }
  102.  
  103. void merge(ptr &t, ptr l, ptr r){
  104. upd(l);
  105. upd(r);
  106. if (l == nullptr){
  107. t = r;
  108. return;
  109. }
  110. if (r == nullptr){
  111. t = l;
  112. return;
  113. }
  114. if (l->y <= r->y)
  115. merge(l->r, l->r, r), t = l;
  116. else
  117. merge(r->l, l, r->l), t = r;
  118. upd(t);
  119. }
  120.  
  121. ptr root = nullptr;
  122.  
  123. int mas[maxn][5];
  124.  
  125. void init(int v, int l, int r){
  126. if (l == r){
  127. q[v].first = mas[l][3];
  128. return;
  129. }
  130. int m = (l + r) / 2;
  131. init(2 * v, l, m);
  132. init(2 * v + 1, m + 1, r);
  133. q[v].first = min(q[2 * v].first, q[2 * v + 1].first);
  134. }
  135.  
  136. ll answer;
  137.  
  138. void insert(ptr &t, ptr ins){
  139. ptr t1, t2;
  140. split(t, t1, t2, ins->v, n);
  141. merge(t, t1, ins);
  142. merge(t, t, t2);
  143. }
  144.  
  145. ptr cpy(ptr t){
  146. ptr ret = new treap;
  147. ret->v = t->v;
  148. ret->y = t->y;
  149. ret->d = t->d;
  150. return ret;
  151. }
  152.  
  153. ptr begin(ptr &t){
  154. if (t->l == nullptr)
  155. return cpy(t);
  156. return begin(t->l);
  157. }
  158.  
  159. int main()
  160. {
  161. ifstream cin("bakery.in");
  162. ofstream cout("bakery.out");
  163. ios::sync_with_stdio(0);
  164. cin >> n;
  165. for (int i = 0; i < n; i++)
  166. cin >> mas[i][0] >> mas[i][1] >> mas[i][2];
  167. for (int i = 0; i < n - 1; i++)
  168. cin >> mas[i][3] >> mas[i][4];
  169. init(1, 0, n - 2);
  170. for (int i = 0; i < n; i++){
  171. ptr ins = create(mas[i][1], mas[i][0], i);
  172. insert(root, ins);
  173. int val = mas[i][2];
  174. while (val > 0){
  175. if (root == nullptr){
  176. cout << -1;
  177. return 0;
  178. }
  179. ptr t1 = begin(root), t2;
  180. split(root, t1, t2, t1->v, t1->d);
  181. ll let = min(t1->m, sum(1, 0, n - 2, t1->d, i - 1));
  182. if (let <= val)
  183. val -= let, root = t2, answer += let * t1->v;
  184. else
  185. answer += val * t1->v, t1->m -= val, update(1, 0, n - 2, t1->d, i - 1, -val), merge(root, t1, t2), val = 0;
  186. }
  187. if (root != nullptr)
  188. root->uv += mas[i][4];
  189. }
  190. cout << answer;
  191. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement