fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define rep(i, a, b) for(int i=(a); i<(b); i++)
  5. #define repi(i, a, b) for(int i=(a); i>(b); i--)
  6. #define db(x) (cerr << #x << ": " << (x) << '\n')
  7. #define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
  8. #define iceil(n, x) (((n) + (x) - 1) / (x))
  9. #define ll long long
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pf push_front
  13. #define pob pop_back
  14. #define pof pop_front
  15. #define sz size()
  16. #define all(v) (v).begin(), (v).end()
  17. #define pii pair<int, int>
  18. #define pll pair<ll, ll>
  19. #define vi vector<int>
  20. #define vll vector<ll, ll>
  21. #define vpii vector<pii>
  22. #define vpll vector<pll>
  23. #define vvi vector<vi>
  24. #define fi first
  25. #define se second
  26. #define umap unordered_map
  27. #define uset unordered_set
  28. #define pqueue priority_queue
  29. #define si(a) scanf("%d", &a)
  30. #define sll(a) scanf("%lld", &a)
  31. #define bitcount(x) __builtin_popcount(x)
  32. #define cps CLOCKS_PER_SEC
  33. #define PI acos(-1.0)
  34. #define EPS 1e-9
  35. #define mod 1000000007
  36. #define MOD 1000000007
  37. #define N 100005
  38. #define M 50
  39. using namespace std;
  40.  
  41. template<typename T>
  42. using minpq = priority_queue<T, vector<T>, greater<T>>;
  43.  
  44. template<typename T>
  45. using maxpq = priority_queue<T>;
  46.  
  47. //All indexing is 0-based
  48. using namespace __gnu_pbds;
  49. typedef tree<pii, null_type, less<pii>, rb_tree_tag,
  50.        tree_order_statistics_node_update> ordered_set;
  51. //methods: find_by_order(k); & order_of_key(k);
  52. //To make it an ordered_multiset, use pairs of (value, time_of_insertion)
  53. //to distinguish values which are similar.
  54.  
  55. //a and b are assumed to be taken modulo p
  56. inline int add(int a, int b, int p = mod){ ll c = a + b; if(c >= p) c -= p; return c;}
  57. inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
  58. inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}
  59.  
  60. int a[N];
  61. int ft[N << 1];
  62. int n;
  63.  
  64. void init() {
  65.   memset(ft, 0, sizeof ft);
  66. }
  67.  
  68. int query(int i) { //prefix sum upto a[i]
  69.   i++;
  70.   int ans = 0;
  71.   while(i > 0) {
  72.     ans += ft[i];
  73.     i -= i & -i;
  74.   }
  75.   return ans;
  76. }
  77.  
  78. int query(int i, int j) { //ranges sum from a[i] .. a[j]
  79.   return query(j) - query(i - 1);
  80. }
  81.  
  82. void increment(int i, int val) {
  83.   i++;
  84.   while(i <= (N << 1)) {
  85.     ft[i] += val;
  86.     i += i &-i;
  87.   }
  88. }
  89.  
  90. void update(int i, int val) {
  91.   int old = query(i, i); //prev value at a[i]
  92.   val = val - old; //total increment for the pos. a[i]
  93.   increment(i, val);
  94. }
  95.  
  96. class MajoritySubarray {
  97. public:
  98.   long long getCount(int n, int seed, int m) {
  99.     ::n = n;
  100.     rep(i, 0, n) {
  101.       a[i] = (seed >> 16) % m;
  102.       //has[a[i]] = 1;
  103.       seed = (seed * 1103515245ll + 12345) & ((1ll << 31) - 1);
  104.     }
  105.     //int bal = n;
  106.     ll ans = 0;
  107.     rep(k, 0, m) {
  108.       int bal = n;
  109.       init();
  110.       rep(i, 0, n) {
  111.         increment(bal, 1);
  112.         if(a[i] == k) bal++;
  113.         else bal--;
  114.         ans += query(bal-1);
  115.         //db(bal), db(k), db(i), db(ans);
  116.       }
  117.     }
  118.     return ans;
  119.   }
  120. };
  121.  
  122.  
  123. main()
  124. { 
  125.   #ifndef ONLINE_JUDGE
  126.     freopen("/home/tarun/Desktop/input.txt", "r", stdin);
  127. //    freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  128.   #endif
  129.   sync;
  130.   clock_t clk = clock();
  131.  
  132.   //cout << MajoritySubarray().getCount(100000, 2147483647, 2) << '\n';
  133.   cout << MajoritySubarray().getCount(100000, 54534555, 50) << '\n';
  134.  
  135.   cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
  136. }
  137.  
  138. //Compile using:
  139. //g++ -o filename.exe --std=c++11 filename.cpp
  140. //Use -D CP for defining a macro CP in the local environment
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
Success #stdin #stdout #stderr 0.13s 16408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
108540
stderr
copy 
Time (in ms): 133.583
https://ideone.com/xayHmk
language:
C++ (gcc 8.3)
created:
6 years 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!