fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. //#define  int long long
  4. #define  all(v) v.begin(),v.end()
  5. using namespace std;
  6. #define ll long long
  7. #define MAX 1000007
  8.  
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11.  
  12. using namespace __gnu_pbds;
  13. template<class T>
  14. using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  15. void erase(ordered_multiset<ll> &st, ll &x){
  16.     st.erase(st.find_by_order(st.order_of_key(x)));
  17. }
  18.  
  19. const int N = 1e3 + 10;
  20. const int SQ = 224;
  21.  
  22. ll x, BIG, SMALL;
  23. struct Mo {
  24.     struct Query {
  25.         int l, r, idx;
  26.         bool operator<(const Query &other) const {
  27.             if (l / SQ != other.l / SQ) return l / SQ < other.l / SQ;
  28.             return (l / SQ & 1 ? r < other.r : r > other.r);
  29.         }
  30.     };
  31.  
  32.     vector<Query> queries;
  33.     vector<long long> res;
  34.     vector<long long> arr;
  35.     ordered_multiset<ll> st;
  36.     int n, q;
  37.     long long ans = 0;
  38.  
  39.     Mo(int _n, int _q) : n(_n), q(_q), arr(_n), res(_q), queries(_q) {}
  40.  
  41.     void add(int idx) {
  42.         ll val = arr[idx];
  43.         int sz = to_string(val).size();
  44.         if(sz == x){
  45.             ll mx = BIG - val;
  46.             ans += st.order_of_key(mx + 1);
  47.         } else if(sz < x){
  48.             ll mx = BIG - val, mn = SMALL - val;
  49.             ans += st.order_of_key(mx + 1) - st.order_of_key(mn);
  50.         }
  51.         st.insert(val);
  52.     }
  53.  
  54.     void remove(int idx) {
  55.         ll val = arr[idx];
  56.         erase(st, val);
  57.         int sz = to_string(val).size();
  58.         if(sz == x){
  59.             ll mx = BIG - val;
  60.             ans -= st.order_of_key(mx + 1);
  61.         } else if(sz < x){
  62.             ll mx = BIG - val, mn = SMALL - val;
  63.             ans -= st.order_of_key(mx + 1) - st.order_of_key(mn);
  64.         }
  65.     }
  66.  
  67.     void build() {
  68.         int L = 0, R = -1;
  69.         sort(queries.begin(), queries.end());
  70.         for (auto &[l, r, idx] : queries) {
  71.             while (R < r) add(++R);
  72.             while (L > l) remove(L++);
  73.             while (R > r) remove(R--);
  74.             while (L > l) add(--L);
  75.             res[idx] = ans;
  76.         }
  77.     }
  78.  
  79.     void input() {
  80.         for (int i = 0; i < q; i++) {
  81.             cin >> queries[i].l >> queries[i].r;
  82.             queries[i].l--;
  83.             queries[i].r--;
  84.             queries[i].idx = i;
  85.         }
  86.     }
  87. };
  88.  
  89.  
  90.  
  91. // 100000000000000000
  92. // 999999999999999999
  93. //
  94. void sol() {
  95.     // INPUT
  96.     int n; cin >> n >> x;
  97.     vector<ll> arr(n);
  98.     for (int i = 0; i < n; ++i) {
  99.         cin >> arr[i];
  100.     }
  101.     BIG = powl(10, x) - 1;
  102.     SMALL = powl(10, x - 1);
  103.     int q; cin >> q;
  104.     Mo mo(n, q);
  105.     mo.arr = arr;
  106.     mo.input();
  107.     mo.build();
  108.     for(auto i : mo.res) cout << i << '\n';
  109. }
  110.  
  111. signed main() {
  112.  
  113.     ios::sync_with_stdio(0);
  114.     cin.tie(0);
  115.     int t = 1;
  116. //    cin >> t;
  117.  
  118.     while (t--) {
  119.         sol();
  120.     }
  121.  
  122. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C8TUUB
language:
C++14 (gcc 8.3)
created:
1 day 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!