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. #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.  
  62. class MajoritySubarray {
  63. public:
  64.   long long getCount(int n, int seed, int m) {
  65.     //::n = n;
  66.     rep(i, 0, n) {
  67.       a[i] = (seed >> 16) % m;
  68.       //has[a[i]] = 1;
  69.       seed = (seed * 1103515245ll + 12345) & ((1ll << 31) - 1);
  70.     }
  71.     //int bal = n;
  72.     ll ans = 0;
  73.     rep(k, 0, m) {
  74.       ordered_set os;
  75.       int bal = 0;
  76.       int t = 0;
  77.       rep(i, 0, n) {
  78.         os.insert({bal, ++t});
  79.         if(a[i] == k) bal++;
  80.         else bal--;
  81.         ans += os.order_of_key({bal, 0});
  82.         //db(bal), db(k), db(i), db(ans);
  83.       }
  84.     }
  85.     return ans;
  86.   }
  87. };
  88.  
  89.  
  90. main()
  91. { 
  92.   #ifndef ONLINE_JUDGE
  93.     freopen("/home/tarun/Desktop/input.txt", "r", stdin);
  94. //    freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  95.   #endif
  96.   sync;
  97.   clock_t clk = clock();
  98.  
  99.   //cout << MajoritySubarray().getCount(100000, 2147483647, 2) << '\n';
  100.   cout << MajoritySubarray().getCount(100000, 54534555, 50) << '\n';
  101.  
  102.   cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
  103. }
  104.  
  105. //Compile using:
  106. //g++ -o filename.exe --std=c++11 filename.cpp
  107. //Use -D CP for defining a macro CP in the local environment
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
Success #stdin #stdout #stderr 1.22s 21968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
108540
stderr
copy 
Time (in ms): 1236.62
https://ideone.com/7CwDne
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!