Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <math.h>
- #include <vector>
- using namespace std;
- vector<long long> a, b;
- vector<long long> prefix_sums_a, prefix_sums_b;
- inline long long sum(vector<long long> const &v, int l, int r) {
- if (l > r) return 0;
- if (l == 0) return v[r];
- return v[r] - v[l - 1];
- }
- inline pair<int, int> intersect(int l1, int r1, int l2, int r2) {
- return {max(l1, l2), min(r1, r2)};
- }
- struct Req {
- char req;
- int l, r;
- Req() {}
- };
- int main() {
- int n;
- cin >> n;
- a.resize(n);
- b.resize(n);
- prefix_sums_a.resize(n);
- prefix_sums_b.resize(n);
- for (int i = 0; i != n; ++i) {
- cin >> a[i];
- }
- for (int i = 0; i != n; ++i) {
- cin >> b[i];
- }
- int m;
- cin >> m;
- int part_size = (n < 1000 ? n : ceill(sqrtl((long double)m)));
- int pp = m;
- vector<Req> reqs(part_size);
- vector<int> open(n);
- vector<int> close(n);
- while (pp != 0) {
- int curr = min(pp, part_size);
- open.assign(n, 0);
- close.assign(n, 0);
- prefix_sums_a[0] = a[0];
- prefix_sums_b[0] = b[0];
- for (int i = 1; i != n; ++i) {
- prefix_sums_a[i] = a[i] + prefix_sums_a[i - 1];
- prefix_sums_b[i] = b[i] + prefix_sums_b[i - 1];
- }
- for (int i = 0; i != curr; ++i) {
- cin >> reqs[i].req >> reqs[i].l >> reqs[i].r;
- int l = reqs[i].l, r = reqs[i].r;
- if (reqs[i].req == '?') {
- long long ans = sum(prefix_sums_a, l, r);
- for (int j = 0; j != i; ++j) {
- if (reqs[j].req == '+') {
- auto inter = intersect(l, r, reqs[j].l, reqs[j].r);
- ans += sum(prefix_sums_b, inter.first, inter.second);
- }
- }
- cout << ans << '\n';
- } else {
- ++open[l];
- ++close[r];
- }
- }
- int bal = 0;
- for (int i = 0; i != n; ++i) {
- bal += open[i];
- a[i] += b[i] * bal;
- bal -= close[i];
- }
- pp -= curr;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement