Advertisement
El_GEMMY

acpc headquarters

Apr 27th, 2022
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.56 KB | None | 0 0
  1. // Those who cannot remember the past are
  2. // condemned to repeat it (use DP -_-)
  3. // - George Santayana
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. #define all(v) v.begin(), v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define ll long long
  15. #define ull unsigned long long
  16. #define MOD 1000000007
  17. #define PI 3.14159265
  18. #define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
  19. #define imin INT_MIN
  20. #define imax INT_MAX
  21. #define llmax LLONG_MAX
  22. #define llmin LLONG_MIN
  23. #define inf 2000000000
  24. #define nl '\n'
  25. #define ppcnt __builtin_popcount
  26. #define ppcntll __builtin_popcountll
  27. #define clz __builtin_clz
  28. #define clzll __builtin_clzll
  29. #define ctz __builtin_ctz
  30. #define ctzll __builtin_ctzll
  31. #define modulo(a, b, mod) ((((a) % (mod)) + ((b) % (mod))) % (mod))
  32. #define cnte(v, x) count(all(v), (x))
  33. #define mine(v) min_element(all(v))
  34. #define maxe(v) max_element(all(v))
  35. #define updmin(a, b) a = min(a, b)
  36. #define updmax(a, b) a = max(a, b)
  37. #define finmod(x, m) x = ((x) % (m) + (m)) % m
  38. #define debug(x) cout << "x: " << (x) << nl;
  39. #define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
  40. #define ordered_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
  41. #define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>
  42.  
  43. //vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
  44. //vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
  45.  
  46. template<typename T = int> istream& operator>>(istream& in, vector<pair<int, int>>& v){
  47.     for (auto& [x, y] : v) in >> x >> y;
  48.     return in;
  49. }
  50.  
  51. template<typename T = int> istream& operator>>(istream& in, vector<T>& v){
  52.     for (T& i : v) in >> i;
  53.     return in;
  54. }
  55.  
  56. template<typename T = int> ostream& operator<<(ostream& out, const vector<T>& v){
  57.     for (const T& x : v)
  58.         out << x << ' ';
  59.     return out;
  60. }
  61.  
  62. template<typename T = pair<int, int>> ostream& operator << (ostream& out, const vector<pair<int, int>>& v){
  63.     for(auto& [x, y] : v){
  64.         out << x << ' ' << y << nl;
  65.     }
  66.     return out;
  67. }
  68.  
  69. void Start_Crushing() {
  70.     ios_base::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.     cout.tie(nullptr);
  73. #ifndef ONLINE_JUDGE
  74.     freopen("input.txt", "r", stdin);
  75.     freopen("output.txt", "w", stdout);
  76. #endif
  77. }
  78.  
  79. void solve(){
  80.     map<string, vector<pair<int, int>>> volunteers;
  81.  
  82.     int n; cin >> n;
  83.     while(n--){
  84.         string contest; cin >> contest;
  85.         int st, ed; cin >> st >> ed;
  86.  
  87.         int num; cin >> num;
  88.         while(num--){
  89.             string name; cin >> name;
  90.             volunteers[name].emplace_back(st, ed);
  91.         }
  92.     }
  93.  
  94.     for(auto& [x, y] : volunteers){
  95.         sort(all(y));
  96.     }
  97.  
  98.     vector<string> conflicts;
  99.  
  100.     for(auto& [x, y] : volunteers){
  101.         int max_end = imin;
  102.  
  103.         for(auto& [s, e] : y){
  104.             if(max_end >= s){
  105.                 conflicts.emplace_back(x);
  106.                 break;
  107.             }
  108.             updmax(max_end, e);
  109.         }
  110.     }
  111.  
  112.     cout << conflicts.size() << nl;
  113.     for(auto& i : conflicts){
  114.         cout << i << nl;
  115.     }
  116. }
  117.  
  118. int main(){
  119.     Start_Crushing();
  120.  
  121.     int t = 1;
  122.     /*Multiple test cases?*/ cin >> t;
  123.     while (t--) {
  124.         solve();
  125.         if(!t)
  126.             break;
  127. //        cout << nl;
  128.     }
  129.  
  130. //    for(int tc = 1; tc <= t; tc++){
  131. //        cout << "Case #" << tc << ": ";
  132. //        solve();
  133. //        if(tc != t)
  134. //            cout << nl;
  135. //    }
  136.  
  137.     return 0;
  138. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement