crap_the_coder

Angry Cyborg C++

Dec 29th, 2020
731
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define endl '\n'
  6.  
  7. signed main() {
  8.     ios::sync_with_stdio(false); cin.tie(NULL);
  9.  
  10.     int tcs; cin >> tcs;
  11.  
  12.     while (tcs--) {
  13.         int n, q; cin >> n >> q;
  14.  
  15.         // ind stores a unique value for each range
  16.         unordered_map<int, vector<int>> ind;
  17.  
  18.         // Unique value for each range
  19.         int unique_val = 1;
  20.  
  21.         while (q--) {
  22.             int l, r; cin >> l >> r;
  23.  
  24.             // Converting to 0-based indexing
  25.             l--;
  26.             r--;
  27.  
  28.             // Positive denotes beginning
  29.             ind[l].push_back(unique_val);
  30.  
  31.             // Negative denotes ending
  32.             // We use r+1 because r is inclusive in the range
  33.             ind[r+1].push_back(-unique_val);
  34.  
  35.             // Next value to make it unique
  36.             unique_val++;
  37.         }
  38.  
  39.         int no_sts = 0;  // Number of statues that will be destroyed
  40.         int ispeed = 0;  // Speed at which the number of statues destroyed increases
  41.  
  42.         // First occurrence of a range (stores l value of a range)
  43.         unordered_map<int, int> occ;
  44.  
  45.         for (int i = 0; i < n; i++) {
  46.             // For each "endpoint" (which is l or r+1)
  47.             for (auto j : ind[i]) {
  48.  
  49.                 // If it's a new range the speed with which the number of statues is destroyed will increase
  50.                 if (j > 0) {
  51.                     occ[j] = i;
  52.                     ispeed++;
  53.                 }
  54.  
  55.                 // If it's the end of a range
  56.                 // The speed with which the number of statues is destroyed will decrease
  57.  
  58.                 // The current amount of statues which are being destroyed at each index will decrease by how much it has contributed
  59.                 // Which is equal to r - l + 1, but since we set the endpoint to r+1, we should make it r - l
  60.                 // Here, (r = i) and (l = [first occurrence of -j] = occ[-j])
  61.                 else if (j < 0) {
  62.                     ispeed--;
  63.                     no_sts -= i - occ[-j];
  64.                 }
  65.             }
  66.  
  67.             // The amount of statues destroyed at each index increases by the speed
  68.             no_sts += ispeed;
  69.  
  70.             cout << no_sts << " ";
  71.         }
  72.  
  73.         cout << endl;
  74.     }
  75. }
  76.  
RAW Paste Data