Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- /*
- Author: Hokimiyon Muhammadjon
- */
- using namespace std;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- struct operation{
- int time = 0;
- double amount = 0.0;
- };
- int maxDate = 3652060;
- int get_date(string s)
- {
- int res = 0;
- int year = 0;
- int month = 0;
- int day = 0;
- for(int i = 0, j = 0; i < static_cast<int>(s.size()); i++){
- if(s[i] == '-'){
- j++;
- }else{
- if(j == 0)year = year * 10 + (s[i] - '0');
- else if(j == 1)month = month * 10 + (s[i] - '0');
- else day = day * 10 + (s[i] - '0');
- }
- }
- if (month < 3) {
- year--;
- month += 12;
- }
- return 365 * year + year / 4 - year / 100 + year / 400 + (153 * month - 457) / 5 + day - 306;
- }
- void countingSort(operation *A, int &n)
- {
- vector<operation> C[maxDate];
- for(int i = 0; i < n; i++){
- C[A[i].time].push_back(A[i]);
- }
- for(int i = 0, id = 0; i < maxDate; i++){
- for(auto x : C[i]){
- A[id++] = x;
- }
- }
- }
- void mergeSort(deque<double> &A, int l, int r)
- {
- if(l == r)return;
- int len = r - l + 1;
- int mid = (l + r) / 2;
- mergeSort(A, l, mid);
- mergeSort(A, mid + 1, r);
- deque<double> B;
- int i = l, j = mid + 1, id = 0;
- while(i <= mid && j <= r){
- if(A[i] <= A[j]){
- B.push_back(A[i++]);
- }else{
- B.push_back(A[j++]);
- }
- }
- while(i <= mid)B.push_back(A[i++]);
- while(j <= r)B.push_back(A[j++]);
- for(int i = 0; i < len; i++){
- A[i + l] = B[i];
- }
- }
- double getMedian(deque <double> &q)
- {
- int len = static_cast<int>(q.size());
- deque<double> A;
- for(int i = 0; i < len; i++){
- A.push_back(q[i]);
- }
- mergeSort(A, 0, len - 1);
- if(len % 2 == 1)return A[len / 2];
- return (A[len / 2] + A[len / 2 - 1]) / 2.0;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- //freopen( "input.txt" , "r" , stdin );
- //freopen( "output.txt" , "w" , stdout );
- int N,D;
- cin >> N >> D;
- operation A[N];
- int id[N];
- int minDate = 1e9;
- double sumDate[maxDate] = {};
- vector<operation> v[maxDate];
- for(int i = 0; i < N; i++){
- string Amount;
- string time;
- cin >> time >> Amount;
- id[i] = i;
- assert(Amount[0] == '$');
- for(int j = 1; j < (int)Amount.size(); j++){
- if(Amount[j] == '.'){
- continue;
- }
- A[i].amount *= 10.0;
- A[i].amount += Amount[j] - '0';
- }
- for(int j = static_cast<int>(Amount.size()) - 1; j >= 0; j--){
- if(Amount[j] == '.')break;
- A[i].amount /= 10.0;
- }
- A[i].time = get_date(time);
- minDate = min(minDate, A[i].time);
- sumDate[A[i].time] += A[i].amount;
- v[A[i].time].push_back(A[i]);
- }
- countingSort(A, N);
- deque<double> q;
- for(int i = minDate; i < minDate + D; i++){
- q.push_back(sumDate[i]);
- }
- int ans = 0;
- for(int i = minDate + D; i < maxDate; i++){
- double res = 0;
- for(auto x : v[i]){
- res += x.amount;
- if(res >= 2.0 * getMedian(q)){
- ans++;
- }
- }
- q.pop_front();
- q.push_back(sumDate[i]);
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment