fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void fileIO() {
  6. #ifndef ONLINE_JUDGE
  7.     freopen("input.txt", "r", stdin);
  8.     freopen("output.txt", "w", stdout);
  9. #endif
  10.  
  11. #ifdef ONLINE_JUDGE
  12.  
  13. #endif
  14. }
  15.  
  16. #define int long long
  17.  
  18. struct node {
  19.     vector<pair<int, int>> v;
  20. };
  21.  
  22. struct merge_sort_tree {
  23.     int n;
  24.     vector<node> tre;
  25.  
  26.     merge_sort_tree(vector<int>& v) {
  27.         int LEN = v.size();
  28.         n = 1;
  29.         while (n < LEN) {
  30.             n <<= 1;
  31.         }
  32.         tre = vector<node>(n << 2, node()), build(v);
  33.     }
  34.  
  35.     node merge(node a, node b) {
  36.         node t;
  37.  
  38.         int x = 0, y = 0;
  39.         while (x < a.v.size() and y < b.v.size()) {
  40.             if (a.v[x].first <= b.v[y].first) {
  41.                 t.v.push_back({ a.v[x].first, a.v[x].first });
  42.                 ++x;
  43.             } else {
  44.                 t.v.push_back({ b.v[y].first, b.v[y].first });
  45.                 ++y;
  46.             }
  47.         }
  48.  
  49.         while (x < a.v.size()) {
  50.             t.v.push_back({ a.v[x].first, a.v[x].first });
  51.             ++x;
  52.         }
  53.  
  54.         while (y < b.v.size()) {
  55.             t.v.push_back({ b.v[y].first, b.v[y].first });
  56.             ++y;
  57.         }
  58.  
  59.         for (int i = 1; i < t.v.size(); ++i) {
  60.             t.v[i].second += t.v[i - 1].second;
  61.         }
  62.  
  63.         return t;
  64.     }
  65.  
  66.     void build(vector<long long>& v, int current_node, int lx, int rx) {
  67.         if (rx - lx == 1) {
  68.             if (lx < v.size()) {
  69.                 tre[current_node].v.push_back({ v[lx], v[lx] });
  70.             }
  71.             return;
  72.         }
  73.  
  74.         int m = (lx + rx) / 2;
  75.         build(v, 2 * current_node + 1, lx, m);
  76.         build(v, 2 * current_node + 2, m, rx);
  77.  
  78.         tre[current_node] = merge(tre[2 * current_node + 1], tre[2 * current_node + 2]);
  79.     }
  80.  
  81.     void build(vector<long long>& v) {
  82.         build(v, 0, 0, n);
  83.     }
  84.  
  85.     pair<int, int> less_than_or_equal(int l, int r, int val, int current_node, int lx, int rx) {
  86.         if (lx >= r or rx <= l) {
  87.             return { 0, 0 };
  88.         }
  89.         if (rx <= r and lx >= l) {
  90.             pair<int, int> p = { val, LLONG_MAX };
  91.             auto it = upper_bound(tre[current_node].v.begin(), tre[current_node].v.end(), p);
  92.             if (it == tre[current_node].v.begin()) {
  93.                 return { 0, 0 };
  94.             } else {
  95.                 return { it - tre[current_node].v.begin(), prev(it)->second };
  96.             }
  97.         }
  98.  
  99.         int m = lx + (rx - lx) / 2;
  100.         int left = current_node * 2 + 1;
  101.         int right = left + 1;
  102.  
  103.         auto a = less_than_or_equal(l, r, val, left, lx, m);
  104.         auto b = less_than_or_equal(l, r, val, right, m, rx);
  105.         pair<int, int> ret = { a.first + b.first, a.second + b.second };
  106.  
  107.         return ret;
  108.     }
  109.  
  110.     pair<int, int> less_than_or_equal(int l, int r, int val) {
  111.         return less_than_or_equal(l, r, val, 0, 0, n);
  112.     }
  113. };
  114.  
  115. void get_shit_done() {
  116.     int n, k;
  117.     cin >> n >> k;
  118.  
  119.     vector<int> v(n);
  120.     map<int, int> fst, lst;
  121.     lst[0] = -1, fst[0] = -1;
  122.     for (int i = 0, pref = 0; i < n; ++i) {
  123.         cin >> v[i];
  124.         pref += v[i];
  125.         if (not fst.count(pref)) {
  126.             fst[pref] = i;
  127.             lst[pref] = i;
  128.         } else {
  129.             lst[pref] = i;
  130.         }
  131.     }
  132.  
  133.     vector<int> gol(n), gor(n);
  134.     for (int i = 0, pref = 0; i < n; ++i) {
  135.         if (fst.count(k + pref)) {
  136.             gol[i] = max(i, fst[k + pref]);
  137.             gor[i] = lst[k + pref];
  138.         } else {
  139.             gol[i] = n;
  140.             gor[i] = n;
  141.         }
  142.         pref += v[i];
  143.     }
  144.     merge_sort_tree L(gol), R(gor);
  145.  
  146.     int q;
  147.     cin >> q;
  148.  
  149.     while (q--) {
  150.         int l, r;
  151.         cin >> l >> r;
  152.  
  153.         --l, --r;
  154.         auto m = L.less_than_or_equal(l, r + 1, r);
  155.         auto p = R.less_than_or_equal(l, r + 1, r);
  156.  
  157.         int calc = p.second + (m.first - p.first) * r - m.second + m.first;
  158.         cout << calc << '\n';
  159.     }
  160. }
  161.  
  162. signed main() {
  163.     fileIO();
  164.     cin.tie(nullptr);
  165.     cout.tie(nullptr);
  166.     ios::sync_with_stdio(false);
  167.  
  168.     int ts = 1;
  169.     cin >> ts;
  170.     for (int tc = 1; tc <= ts; ++tc) {
  171.         get_shit_done();
  172.     }
  173.  
  174.     return 0;
  175. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RCURaE
language:
C++ (gcc 8.3)
created:
53 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!