fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef unsigned int uint;
  9. typedef long long ll;
  10. typedef unsigned long long ull;
  11. typedef long double ld;
  12. typedef vector<ll> vll;
  13. typedef vector<char> vc;
  14. typedef vector<bool> vb;
  15. typedef vector<vll> vvll;
  16. typedef vector<vector<char>> vvc;
  17.  
  18.  
  19. #define int ll
  20. #define sz(s) (ll)s.size()
  21. #define all(s) (s).begin(),(s).end()
  22. #define rall(s) (s).begin(),(s).end(),greater<>()
  23. #define ln '\n'
  24. #define rtv(n) return void(cout<<n)
  25. #define fixset(n) cout<<fixed<<setprecision(n)
  26. #define getunique(v){sort(all(v));v.erase(unique(all(v)), v.end());}
  27. #define input(a) for(auto&it:a)cin>>it;
  28. #define print(a) for(auto&it:a)cout<<it<<" ";cout<<ln;
  29.  
  30.  
  31. const int MOD = 1e9 + 7;
  32. const int MX = 2e5 + 5;
  33.  
  34.  
  35. void Sayman369() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(nullptr);
  38.     cout.tie(nullptr);
  39. }
  40.  
  41. void file() {
  42. #ifdef LOCAL
  43.     freopen("input.txt", "r", stdin);
  44.     freopen("output.txt", "w", stdout);
  45. #else
  46.     //        freopen("mex.in", "r", stdin);
  47.     //        freopen("output.txt", "w", stdout);
  48. #endif
  49. }
  50.  
  51.  
  52. void preprocessing() {
  53. }
  54.  
  55.  
  56. template <class T>
  57. using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  58. // less: it is the basic for comparison of two function. Use less_equal for ordered multiset.
  59. // order_of_key(k): Number of items strictly smaller than k
  60. // find_by_order(k): kth element in a set (counting from zero)
  61.  
  62. ll add(int a, int b, int m) {
  63.     return ((a % m) + (b % m)) % m;
  64. }
  65.  
  66. ll mul(int a, int b, int m) {
  67.     return ((a % m) * (b % m)) % m;
  68. }
  69.  
  70. void solve(int tc) {
  71.     int a, b, c, n;
  72.     cin >> a >> b >> c >> n;
  73.     ordered_set<int> st;
  74.     vll f(n + 1);
  75.     f[1] = 1;
  76.     st.insert(f[1]);
  77.     for (int i = 2; i <= n; i++) {
  78.         int x = *st.find_by_order(sz(st) / 2 - !(sz(st) & 1));
  79.         f[i] = ((a * x) + (b * i) + c);
  80.         if (f[i] >= MOD)f[i] -= MOD;
  81.         st.insert(f[i]);
  82.     }
  83.     cout << accumulate(all(f), 0ll) << ln;
  84. }
  85.  
  86. signed main() {
  87.     Sayman369();
  88.     file();
  89.     preprocessing();
  90.     int tc = 1;
  91.     cin >> tc;
  92.     for (int i = 1; i <= tc; i++) {
  93.         solve(i);
  94.     }
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/hJBoar
language:
C++14 (gcc 8.3)
created:
2 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!