Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5 + 100, inf = 1e9 + 100, mod = 1e9 + 993;
- int n;
- pair<int, int> q[4 * maxn];
- void upd(int v, int l, int r){
- if (q[v].second == 0)
- return;
- q[v].first += q[v].second;
- int m = (l + r) / 2;
- if (l != m)
- q[2 * v].second += q[v].second;
- if (r != m)
- q[2 * v + 1].second += q[v].second;
- q[v].second = 0;
- }
- void update(int v, int tl, int tr, int l, int r, int val){
- upd(v, tl, tr);
- if (l > r)
- return;
- if (tl == l && tr == r){
- q[v].second += val;
- upd(v, tl, tr);
- return;
- }
- int m = (tl + tr) / 2;
- update(2 * v, tl, m, l, min(r, m), val);
- update(2 * v + 1, m + 1, tr, max(l, m + 1), r, val);
- q[v].first = min(q[2 * v].first, q[2 * v + 1].first);
- }
- ll sum(int v, int tl, int tr, int l, int r){
- upd(v, tl, tr);
- if (l > r)
- return inf;
- if (tl == l && tr == r)
- return q[v].first;
- int m = (tl + tr) / 2;
- return min(sum(2 * v, tl, m, l, min(r, m)), sum(2 * v + 1, m + 1, tr, max(l, m + 1), r));
- }
- struct treap{
- ll v, uv, m, d, y;
- treap *l, *r;
- };
- typedef treap * ptr;
- ptr create(int v, int m, int d){
- ptr t = new treap;
- t->v = v;
- t->uv = -1;
- t->m = m;
- t->d = d;
- t->l = nullptr;
- t->r = nullptr;
- t->y = rand();
- return t;
- }
- void upd(ptr &t){
- if (t == nullptr)
- return;
- if (t->uv != -1){
- t->v += t->uv;
- if (t->l != nullptr)
- if (t->l->uv == -1)
- t->l->uv = t->uv;
- else
- t->l->uv += t->uv;
- if (t->r != nullptr)
- if (t->r->uv == -1)
- t->r->uv = t->uv;
- else
- t->r->uv += t->uv;
- t->uv = -1;
- }
- }
- void split(ptr t, ptr &l, ptr &r, int v, int d){
- if (t == nullptr){
- l = nullptr;
- r = nullptr;
- return;
- }
- upd(t);
- if (t->v < v || (t->v == v && t->d <= d))
- split(t->r, t->r, r, v, d), l = t;
- else
- split(t->l, l, t->l, v, d), r = t;
- upd(l);
- upd(r);
- }
- void merge(ptr &t, ptr l, ptr r){
- upd(l);
- upd(r);
- if (l == nullptr){
- t = r;
- return;
- }
- if (r == nullptr){
- t = l;
- return;
- }
- if (l->y <= r->y)
- merge(l->r, l->r, r), t = l;
- else
- merge(r->l, l, r->l), t = r;
- upd(t);
- }
- ptr root = nullptr;
- int mas[maxn][5];
- void init(int v, int l, int r){
- if (l == r){
- q[v].first = mas[l][3];
- return;
- }
- int m = (l + r) / 2;
- init(2 * v, l, m);
- init(2 * v + 1, m + 1, r);
- q[v].first = min(q[2 * v].first, q[2 * v + 1].first);
- }
- ll answer;
- void insert(ptr &t, ptr ins){
- ptr t1, t2;
- split(t, t1, t2, ins->v, n);
- merge(t, t1, ins);
- merge(t, t, t2);
- }
- ptr cpy(ptr t){
- ptr ret = new treap;
- ret->v = t->v;
- ret->y = t->y;
- ret->d = t->d;
- return ret;
- }
- ptr begin(ptr &t){
- if (t->l == nullptr)
- return cpy(t);
- return begin(t->l);
- }
- int main()
- {
- ifstream cin("bakery.in");
- ofstream cout("bakery.out");
- ios::sync_with_stdio(0);
- cin >> n;
- for (int i = 0; i < n; i++)
- cin >> mas[i][0] >> mas[i][1] >> mas[i][2];
- for (int i = 0; i < n - 1; i++)
- cin >> mas[i][3] >> mas[i][4];
- init(1, 0, n - 2);
- for (int i = 0; i < n; i++){
- ptr ins = create(mas[i][1], mas[i][0], i);
- insert(root, ins);
- int val = mas[i][2];
- while (val > 0){
- if (root == nullptr){
- cout << -1;
- return 0;
- }
- ptr t1 = begin(root), t2;
- split(root, t1, t2, t1->v, t1->d);
- ll let = min(t1->m, sum(1, 0, n - 2, t1->d, i - 1));
- if (let <= val)
- val -= let, root = t2, answer += let * t1->v;
- else
- answer += val * t1->v, t1->m -= val, update(1, 0, n - 2, t1->d, i - 1, -val), merge(root, t1, t2), val = 0;
- }
- if (root != nullptr)
- root->uv += mas[i][4];
- }
- cout << answer;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement