fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. typedef long long int ll;
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8. #define fastio ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
  9.  
  10. typedef tree< pair < ll, ll >, null_type, less< pair < ll, ll > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  11.  
  12. const ll mod = 1e9+7;
  13. const ll MAXN = 1e5+5;
  14. const ll inf = 1e18;
  15.  
  16. int main()
  17. {
  18.     fastio;
  19.     ll n;
  20.     cin >> n;
  21.     vector < ll > x(n);
  22.     for(int i = 0; i < n; i++) cin >> x[i];
  23.     ll len = (ll)sqrt(n) + 1;
  24.     vector < ordered_set > s(len);
  25.     for(int i = 0; i< n; i++){
  26.         s[i / len].insert({x[i], i});
  27.     }
  28.     ll q;
  29.     cin >> q;
  30.     while(q--){
  31.         ll a;
  32.         cin >> a;
  33.         if(a == 0){
  34.             ll l, r, y, ans = 0;
  35.             cin >> l >> r >> y;
  36.             l--; r--;/*
  37.             for(int i = l; i <= r; ){
  38.                 if(i % len == 0 && i + len - 1 <= r){
  39.                     ans += s[i / len].size() - s[i / len].order_of_key({y, -inf});
  40.                     i += len;
  41.                 }else{
  42.                     if(x[i] >= y) ans++;
  43.                     i++;
  44.                 }
  45.             }*/
  46.             ll c_l = l / len, c_r = r / len;
  47.             if(c_l == c_r){
  48.                 for(int i = l; i <= r; i++){
  49.                     if(x[i] >= y) ans++;
  50.                 }
  51.                 cout << ans << endl;
  52.                 continue;
  53.             }
  54.             for(int i = l; i < (c_l + 1) * len; i++){
  55.                 if(x[i] >= y) ans++;
  56.             }
  57.             for(int i = (c_l + 1); i <= (c_r - 1); i++){
  58.                 ans += s[i].size() - s[i].order_of_key({y, -inf});
  59.             }
  60.             for(int i = (c_r) * len; i <= r; i++){
  61.                 if(x[i] >= y) ans++;
  62.             }
  63.             cout << ans << endl;
  64.         }else{
  65.             ll ind, val;
  66.             cin >> ind >> val;
  67.             ind--;
  68.             s[ind / len].erase({x[ind], ind});
  69.             s[ind / len].insert({val, ind});
  70.             x[ind] = val;
  71.         }
  72.     }
  73. }
  74.  
Runtime error #stdin #stdout #stderr 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/5XUhVm
problem GIVEAWAY, based on SPOJ submission 25603189 (CPP14), 2020-03-22 18:38:30
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!