Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- #include <string>
- #include <sstream>
- #include <algorithm>
- #include <iostream>
- #include <iomanip>
- #include <map>
- #include <set>
- #include <list>
- #include <queue>
- #include <stack>
- #include <vector>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define REP(i, n) for (int i = 0; i < (int)(n); i++)
- #define foreach(e, x) for (__typeof(x.begin()) e = x.begin(); e != x.end(); e++)
- typedef long long LL;
- typedef pair<int, int> PII;
- struct Vertex {
- Vertex *left, *right;
- LL x, y;
- Vertex(LL x = 0, LL y = 0) : left(NULL), right(NULL), x(x), y(y) {}
- Vertex(Vertex *l, Vertex *r, LL x = 0, LL y = 0) : left(l), right(r), x(x), y(y) {}
- };
- const LL INF = 1e10;
- int n, m;
- Vertex *t[100001];
- int a[100000];
- Vertex *build_st(int L, int R) {
- if (L == R) return new Vertex(a[L]);
- int mid = (L + R) >> 1;
- return new Vertex(build_st(L, mid), build_st(mid + 1, R));
- }
- Vertex *update_st(Vertex *t, int L, int R, int l, int r, LL x, LL y) {
- if (l == L && r == R)
- return new Vertex(t->left, t->right, min(t->x + x, INF), t->y + y);
- int mid = (L + R) >> 1;
- Vertex *newl = t->left, *newr = t->right;
- if (l <= mid)
- newl = update_st(t->left, L, mid, l, min(r, mid), x, y);
- if (r >= mid + 1)
- newr = update_st(t->right, mid + 1, R, max(l, mid + 1), r, x + max(0, mid - l + 1) * y, y);
- return new Vertex(newl, newr, t->x, t->y);
- }
- LL query_st(Vertex *t, int L, int R, int pos, LL x, LL y) {
- if (L == R) return t->x + x;
- int mid = (L + R) >> 1;
- if (pos <= mid) return query_st(t->left, L, mid, pos, x + t->x, y + t->y);
- return query_st(t->right, mid + 1, R, pos, min(x + t->x + (R - mid) * (y + t->y), INF), y + t->y);
- }
- int main() {
- scanf("%d", &n);
- REP(i, n) scanf("%d", a + i);
- int R = 1;
- while (R < n) R <<= 1;
- --R;
- t[0] = build_st(0, R);
- scanf("%d", &m);
- for (int query = 1; query <= m; ++query) {
- int l, r, x, y;
- scanf("%d%d%d%d", &l, &r, &x, &y), --l, --r;
- t[query] = update_st(t[query - 1], 0, R, l, r, x, y);
- }
- REP(i, n) {
- int l = 0, r = m + 1, mid;
- while (l < r) {
- mid = (l + r) >> 1;
- if (query_st(t[mid], 0, R, i, 0, 0) < 0)
- l = mid + 1;
- else
- r = mid;
- }
- if (l == m + 1) printf("-1 ");
- else printf("%d ", l);
- }
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement