Advertisement
iskhakovt

Untitled

Apr 13th, 2015
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <math.h>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. vector<long long> a, b;
  9. vector<long long> prefix_sums_a, prefix_sums_b;
  10.  
  11. inline long long sum(vector<long long> const &v, int l, int r) {
  12.     if (l > r) return 0;
  13.     if (l == 0) return v[r];
  14.     return v[r] - v[l - 1];
  15. }
  16.  
  17. inline pair<int, int> intersect(int l1, int r1, int l2, int r2) {
  18.     return {max(l1, l2), min(r1, r2)};
  19. }
  20.  
  21. struct Req {
  22.     char req;
  23.     int l, r;
  24.     Req() {}
  25. };
  26.  
  27. int main() {
  28.     int n;
  29.     cin >> n;
  30.    
  31.     a.resize(n);
  32.     b.resize(n);
  33.     prefix_sums_a.resize(n);
  34.     prefix_sums_b.resize(n);
  35.    
  36.     for (int i = 0; i != n; ++i) {
  37.         cin >> a[i];
  38.     }
  39.     for (int i = 0; i != n; ++i) {
  40.         cin >> b[i];
  41.     }
  42.    
  43.     int m;
  44.     cin >> m;
  45.    
  46.     int part_size = (n < 1000 ? n : ceill(sqrtl((long double)m)));
  47.     int pp = m;
  48.    
  49.     vector<Req> reqs(part_size);
  50.     vector<int> open(n);
  51.     vector<int> close(n);
  52.    
  53.     while (pp != 0) {
  54.         int curr = min(pp, part_size);
  55.        
  56.         open.assign(n, 0);
  57.         close.assign(n, 0);
  58.        
  59.         prefix_sums_a[0] = a[0];
  60.         prefix_sums_b[0] = b[0];
  61.        
  62.         for (int i = 1; i != n; ++i) {
  63.             prefix_sums_a[i] = a[i] + prefix_sums_a[i - 1];
  64.             prefix_sums_b[i] = b[i] + prefix_sums_b[i - 1];
  65.         }
  66.        
  67.         for (int i = 0; i != curr; ++i) {
  68.             cin >> reqs[i].req >> reqs[i].l >> reqs[i].r;
  69.            
  70.             int l = reqs[i].l, r = reqs[i].r;
  71.            
  72.             if (reqs[i].req == '?') {
  73.                 long long ans = sum(prefix_sums_a, l, r);
  74.                
  75.                 for (int j = 0; j != i; ++j) {
  76.                     if (reqs[j].req == '+') {
  77.                         auto inter = intersect(l, r, reqs[j].l, reqs[j].r);
  78.                         ans += sum(prefix_sums_b, inter.first, inter.second);
  79.                     }
  80.                 }
  81.                
  82.                 cout << ans << '\n';
  83.             } else {
  84.                 ++open[l];
  85.                 ++close[r];
  86.             }
  87.         }
  88.        
  89.         int bal = 0;
  90.         for (int i = 0; i != n; ++i) {
  91.             bal += open[i];
  92.             a[i] += b[i] * bal;
  93.             bal -= close[i];
  94.         }
  95.        
  96.         pp -= curr;
  97.     }
  98.    
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement