Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- #include<memory.h>
- using namespace std;
- typedef long long ll;
- const int N = 100000 + 10;
- const int sq = 333;
- int res[N], a[N], b[N], l[N], r[N];
- ll x[N], y[N], xx[N], yy[N], need[N];
- int main()
- {
- ios_base::sync_with_stdio(true);
- freopen("jam.in", "r", stdin);
- freopen("jam.out", "w", stdout);
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++) cin >> a[i];
- for (int i = 1; i <= n; i++) cin >> b[i];
- for (int i = 1; i <= n; i++) res[i] = -1;
- for (int i = 1; i <= n; i++)
- {
- need[i] = b[i] - a[i];
- if (need[i] <= 0) res[i] = 0;
- }
- int m;
- cin >> m;
- for (int i = 1; i <= m; i++) cin >> l[i] >> r[i] >> x[i] >> y[i];
- for (int lf = 1; lf <= m; lf += sq)
- {
- int rh = std::min(lf + sq - 1, m);
- memset(xx, 0, sizeof(xx));
- memset(yy, 0, sizeof(yy));
- for (int i = lf; i <= rh; i++)
- {
- xx[l[i]] += x[i] - y[i];
- yy[l[i]] += y[i];
- xx[r[i] + 1] -= x[i] + y[i] * (r[i] - l[i]);
- yy[r[i] + 1] -= y[i];
- }
- ll sum = 0, coef = 0;
- for (int i = 1; i <= n; i++)
- {
- coef += yy[i];
- sum += xx[i] + coef;
- if (res[i] != -1) continue;
- if (need[i] <= sum)
- for (int j = lf; j <= rh; j++)
- {
- if (!(l[j] <= i && i <= r[j])) continue;
- need[i] -= x[j] + y[j] * (i - l[j]);
- if (need[i] <= 0) { res[i] = j; break; }
- }
- else need[i] -= sum;
- }
- }
- for (int i = 1; i <= n; i++) cout << res[i] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement