willy108

SPOJ KQUERY

Oct 16th, 2021
1,093
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. //chtholly and emilia will carry me to cm
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <utility>
  7. #include <cassert>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <array>
  11. #include <tuple>
  12.  
  13. #define ll long long
  14. #define lb long double
  15. #define sz(vec) ((int)(vec.size()))
  16. #define all(x) x.begin(), x.end()
  17. #define LC(k) (2*(k) +1)
  18. #define RC(k) (2*(k) +2)
  19.  
  20. const lb eps = 1e-9;
  21. const ll mod = 1e9 + 7, ll_max = 1e18;
  22. //const ll mod = (1 << (23)) * 119 +1;
  23. const int MX = 3e5 +10, int_max = 0x3f3f3f3f;
  24.  
  25. using namespace std;
  26.  
  27. //i will learn from moo.
  28. /* Input */
  29. template<class T> void read(T &x) { cin >> x; }
  30. template<class H, class T> void read(pair<H, T> &p) { cin >> p.first >> p.second; }
  31. template<class T, size_t S> void read(array<T, S> &a) { for (T &i : a) read(i); }
  32. template<class T> void read(vector<T> &v) { for (T &i : v) read(i); }
  33.  
  34. template<class H, class... T> void read(H &h, T &...t) { read(h); read(t...); }
  35.  
  36. /* Output */
  37. template<class H, class T> ostream &operator<<(ostream &o, pair<H, T> &p) { o << p.first << " " << p.second; return o; }
  38. template<class T, size_t S> ostream &operator<<(ostream &o, array<T, S> &a) { string s; for (T i : a) o << s << i, s = " "; return o; }
  39. template<class T> ostream &operator<<(ostream &o, vector<T> &v) { string s; for (T i : v) o << s << i, s = " "; return o; }
  40.  
  41. template<class T> void write(T x) { cout << x; }
  42. template<class H, class... T> void write(const H &h, const T &...t) { write(h); write(t...); }
  43.  
  44. void print() { write('\n'); }
  45. template<class H, class... T> void print(const H &h, const T &...t) { write(h); if (sizeof...(t)) write(' '); print(t...); }
  46.  
  47. /* Misc */
  48. template <typename T> void ckmin(T &a, const T &b) { a = min(a, b); }
  49. template <typename T> void ckmax(T &a, const T &b) { a = max(a, b); }
  50.  
  51. int sum[MX*4], arr[MX], srt[MX*2], ans[MX];
  52. int n, q, mm;
  53.  
  54. vector<pair<int, int>> adj[MX*2];
  55.  
  56. void U(int k, int v){
  57.     for(; k<=mm*2; k += (k&(-k))) sum[k] += v;
  58. }
  59. int S(int k){
  60.     return (!k) ? 0 : (sum[k] + S(k - (k&(-k))));
  61. }
  62.  
  63. int llb(int k){
  64.     return 1 + lower_bound(srt, srt + mm, k) - srt;
  65. }  
  66.  
  67. void solve(){
  68.     read(n);
  69.     for(int i = 0; i<n; i++) read(arr[i]);
  70.     read(q);
  71.     for(int i = 0; i<q; i++){
  72.         int a, b, c;
  73.         read(a, b, c);
  74.         srt[i] = c;
  75.         if(a > 1) adj[a - 2].push_back(make_pair(-c, i));
  76.         adj[b - 1].push_back(make_pair(c, i));
  77.     }
  78.     for(int i = 0; i<n; i++) srt[q+i] = arr[i];
  79.     srt[n+q] = int_max;
  80.     sort(srt, srt + n+q+1);
  81.     mm = unique(srt, srt + n+q+1) - srt;
  82.     //print(vector<int>(srt, srt + mm));
  83.     for(int i = 0; i<n; i++){
  84.         U(llb(arr[i]), 1);
  85.         for(auto e : adj[i]){
  86.             int x = e.first, j = e.second;
  87.             int v = x/abs(x);
  88.             x /= v;
  89.             ans[j] += v * (S(llb(int_max)) - S(llb(x)));
  90.             //print(x, i, v, S(llb(x)), llb(x));
  91.         }
  92.     }
  93.     for(int i = 0; i<q; i++){
  94.         print(ans[i]);
  95.     }
  96. }
  97.  
  98. int main(){
  99.   cin.tie(0) -> sync_with_stdio(0);
  100.     int T = 1;
  101.     //cin >> T;
  102.   while(T--){
  103.         solve();
  104.     }
  105.     return 0;
  106. }
  107.  
  108.  
  109.  
RAW Paste Data