fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. using namespace std;
  10.  
  11. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  12. #define rand rd
  13.  
  14. long long Rand(long long l , long long h){
  15.     assert(l <= h);
  16.     return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  17. }
  18.  
  19. const int MAX = 1e5 + 5;
  20. int BIT[MAX] , sum[MAX];
  21. int res[MAX];
  22. int q;
  23.  
  24. struct node{
  25.     int l , r , x , i;
  26. };
  27.  
  28. vector <node> query;
  29. vector <ii> save;
  30.  
  31. bool cmp(ii a , ii b){
  32.     return a.se > b.se;
  33. }
  34.  
  35. bool dk(node a , node b){
  36.     return a.x > b.x;
  37. }
  38.  
  39. void build(){
  40.     for(int i = 1 ; i * 2 <= 1e5 ; i++){
  41.         for(int j = i * 2 ; j <= 1e5 ; j += i) sum[j] += i;
  42.     }
  43.     for(int i = 1 ; i <= 1e5 ; i++){
  44.         save.push_back({i , sum[i]});
  45.     }
  46.     sort(all(save) , cmp);
  47. }
  48.  
  49. void update(int vt){
  50.     while(vt < MAX){
  51.         BIT[vt]++;
  52.         vt += vt & -vt;
  53.     }
  54. }
  55.  
  56. int GET(int vt){
  57.     int sum = 0;
  58.     while(vt > 0){
  59.         sum += BIT[vt];
  60.         vt -= vt & -vt;
  61.     }
  62.     return sum;
  63. }
  64.  
  65. void INP(){
  66.     build();
  67.     cin >> q;
  68.     for(int i = 1 ; i <= q ; i++){
  69.         int l , r , x;
  70.         cin >> l >> r >> x;
  71.         query.push_back({l , r , x , i});
  72.     }
  73.     sort(all(query) , dk);
  74.     int vt = 0;
  75.     for(auto x : save){
  76.         while(vt < q && query[vt].x >= x.se){
  77.             node tmp = query[vt++];
  78.             //cout << GET(tmp.r) << ' '  << GET(tmp.l - 1) << ' ' << x.se << ' ' << tmp.x << endl;
  79.             res[tmp.i] = GET(tmp.r) - GET(tmp.l - 1);
  80.         }
  81.         update(x.fi);
  82.     }
  83.     for(int i = 1 ; i <= q ; i++) cout << res[i] << endl;
  84. }
  85.  
  86.  
  87. int main()
  88. {
  89.     ios_base::sync_with_stdio(false);
  90.     cin.tie(0);
  91.     cout.tie(0);
  92.     #define TASK ""
  93.     //freopen(TASK".inp" , "r" , stdin);
  94.     //freopen(TASK".out" , "w" , stdout);
  95.     INP();
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.02s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/CeAklP
language:
C++14 (gcc 8.3)
created:
20 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!