1-ShadowMaster-1

Untitled

Apr 16th, 2022
652
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. /*
  4.  
  5.         Author: Hokimiyon Muhammadjon
  6.  
  7. */
  8.  
  9. using namespace std;
  10.  
  11.  
  12. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  13.  
  14. struct operation{
  15.         int time = 0;
  16.         double amount = 0.0;
  17. };
  18.  
  19. int maxDate = 3652060;
  20.  
  21. int get_date(string s)
  22. {
  23.         int res = 0;
  24.         int year = 0;
  25.         int month = 0;
  26.         int day = 0;
  27.         for(int i = 0, j = 0; i < static_cast<int>(s.size()); i++){
  28.                 if(s[i] == '-'){
  29.                         j++;
  30.                 }else{
  31.                         if(j == 0)year = year * 10 + (s[i] - '0');
  32.                         else if(j == 1)month = month * 10 + (s[i] - '0');
  33.                         else day = day * 10 + (s[i] - '0');
  34.                 }
  35.         }
  36.         if (month < 3) {
  37.                 year--;
  38.                 month += 12;
  39.         }
  40.         return 365 * year + year / 4 - year / 100 + year / 400 + (153 * month - 457) / 5 + day - 306;
  41. }
  42.  
  43. void countingSort(operation *A, int &n)
  44. {
  45.         vector<operation> C[maxDate];
  46.         for(int i = 0; i < n; i++){
  47.                 C[A[i].time].push_back(A[i]);
  48.         }
  49.         for(int i = 0, id = 0; i < maxDate; i++){
  50.                 for(auto x : C[i]){
  51.                         A[id++] = x;
  52.                 }
  53.         }
  54. }
  55.  
  56. void mergeSort(deque<double> &A, int l, int r)
  57. {
  58.         if(l == r)return;
  59.         int len = r - l + 1;
  60.         int mid = (l + r) / 2;
  61.         mergeSort(A, l, mid);
  62.         mergeSort(A, mid + 1, r);
  63.         deque<double> B;
  64.         int i = l, j = mid + 1, id = 0;
  65.         while(i <= mid && j <= r){
  66.                 if(A[i] <= A[j]){
  67.                         B.push_back(A[i++]);
  68.                 }else{
  69.                         B.push_back(A[j++]);
  70.                 }
  71.         }
  72.         while(i <= mid)B.push_back(A[i++]);
  73.         while(j <= r)B.push_back(A[j++]);
  74.         for(int i = 0; i < len; i++){
  75.                 A[i + l] = B[i];
  76.         }
  77. }
  78.  
  79. double getMedian(deque <double> &q)
  80. {
  81.         int len = static_cast<int>(q.size());
  82.         deque<double> A;
  83.         for(int i = 0; i < len; i++){
  84.                 A.push_back(q[i]);
  85.         }
  86.         mergeSort(A, 0, len - 1);
  87.         if(len % 2 == 1)return A[len / 2];
  88.         return (A[len / 2] + A[len / 2 - 1]) / 2.0;
  89. }
  90.  
  91. int main()
  92. {
  93.         ios_base::sync_with_stdio(false);
  94.         cin.tie(NULL);
  95.         //freopen( "input.txt" , "r" , stdin );
  96.         //freopen( "output.txt" , "w" , stdout );
  97.  
  98.         int N,D;
  99.         cin >> N >> D;
  100.         operation A[N];
  101.         int id[N];
  102.         int minDate = 1e9;
  103.         double sumDate[maxDate] = {};
  104.         vector<operation> v[maxDate];
  105.         for(int i = 0; i < N; i++){
  106.                 string Amount;
  107.                 string time;
  108.                 cin >> time >> Amount;
  109.                 id[i] = i;
  110.                 assert(Amount[0] == '$');
  111.                 for(int j = 1; j < (int)Amount.size(); j++){
  112.                         if(Amount[j] == '.'){
  113.                                 continue;
  114.                         }
  115.                         A[i].amount *= 10.0;
  116.                         A[i].amount += Amount[j] - '0';
  117.                 }
  118.                 for(int j = static_cast<int>(Amount.size()) - 1; j >= 0; j--){
  119.                         if(Amount[j] == '.')break;
  120.                         A[i].amount /= 10.0;
  121.                 }
  122.                 A[i].time = get_date(time);
  123.                 minDate = min(minDate, A[i].time);
  124.                 sumDate[A[i].time] += A[i].amount;
  125.                 v[A[i].time].push_back(A[i]);
  126.         }
  127.         countingSort(A, N);
  128.         deque<double> q;
  129.         for(int i = minDate; i < minDate + D; i++){
  130.                 q.push_back(sumDate[i]);
  131.         }
  132.         int ans = 0;
  133.         for(int i = minDate + D; i < maxDate; i++){
  134.                 double res = 0;
  135.                 for(auto x : v[i]){
  136.                         res += x.amount;
  137.                         if(res >= 2.0 * getMedian(q)){
  138.                                ans++;
  139.                         }
  140.                 }
  141.                 q.pop_front();
  142.                 q.push_back(sumDate[i]);
  143.         }
  144.         cout << ans;
  145. }
  146.  
  147.  
Advertisement
Add Comment
Please, Sign In to add comment