paradox64ce

Round D-C

Jul 12th, 2021
678
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Miles Morales : When will I know I'm ready?
  3. Peter B. Parker : You won't. It's a leap of faith. That's all it is, Miles. A leap of faith.
  4. */
  5. //KEEP IT SIMPLE STUPID
  6.  
  7. #include <bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. /*================PRAGMAS START===============================================*/
  12. #pragma GCC optimize("O3")
  13. #pragma GCC target("avx")
  14. #pragma GCC optimize("Ofast")
  15. #pragma GCC optimize("unroll-loops")
  16. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  17. /*================PRAGMAS END===============================================*/
  18.  
  19. /*=================DEFINES/TYPEDEF START==============================*/
  20. #define int long long
  21. #define FIO                           \
  22.     freopen("input.txt", "r", stdin); \
  23.     freopen("output.txt", "w", stdout);
  24. #define Lightspeed           \
  25.     ios::sync_with_stdio(0); \
  26.     cin.tie(0);              \
  27.     cout.tie(0);
  28. #define google cout << "Case #" << tt << ": "
  29. #define umin(...) min({__VA_ARGS__})
  30. #define umax(...) max({__VA_ARGS__})
  31. #define MAX(v) *max_element(all(v))
  32. #define MIN(v) *min_element(all(v))
  33. #define fi first
  34. #define se second
  35. /*=================DEFINES/TYPEDEF END================================*/
  36.  
  37. /*=================DEBUGGING START====================================*/
  38. vector<string> split(const string &s, char c)
  39. {
  40.     vector<string> v;
  41.     stringstream ss(s);
  42.     string x;
  43.     while (getline(ss, x, c))
  44.         v.emplace_back(x);
  45.     return move(v);
  46. }
  47. template <typename T, typename... Args>
  48. inline string arrStr(T arr, int n)
  49. {
  50.     stringstream s;
  51.     s << "[";
  52.     for (int i = 0; i < n - 1; i++)
  53.         s << arr[i] << ",";
  54.     s << arr[n - 1] << "]";
  55.     return s.str();
  56. }
  57.  
  58. #ifndef ONLINE_JUDGE
  59. #define debug(args...)                            \
  60.     {                                             \
  61.         __evars_begin(__LINE__);                  \
  62.         __evars(split(#args, ',').begin(), args); \
  63.     }
  64.  
  65. inline void __evars_begin(int line)
  66. {
  67.     cerr << "#" << line << ": ";
  68. }
  69. template <typename T>
  70. inline void __evars_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
  71. template <typename T>
  72. inline void __evars_out_var(T *val) { cerr << arrStr(val, 10); }
  73. template <typename T>
  74. inline void __evars_out_var(T val) { cerr << val; }
  75. inline void __evars(vector<string>::iterator it) { cerr << endl; }
  76.  
  77. template <typename T, typename... Args>
  78. inline void __evars(vector<string>::iterator it, T a, Args... args)
  79. {
  80.     cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  81.     __evars_out_var(a);
  82.     cerr << "; ";
  83.     __evars(++it, args...);
  84. }
  85. // #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
  86. #else
  87. #define debug(...) 42
  88. #endif
  89.  
  90. /*===============================DEBUGGING END======================*/
  91.  
  92. /*=======================CONSTANTS START============================*/
  93. const int INF = 1e18;
  94. const int MOD = 1e9 + 7;
  95. /*=======================CONSTANTS END==============================*/
  96.  
  97. /*======================SOME USEFUL FUNCTIONS START=======================*/
  98. void usaco(string prob)
  99. {
  100.     freopen((prob + ".in").c_str(), "r", stdin);
  101.     freopen((prob + ".out").c_str(), "w", stdout);
  102. }
  103.  
  104. int gcd(int a, int b)
  105. {
  106.     return __gcd(a, b);
  107. }
  108.  
  109. int lcm(int a, int b)
  110. {
  111.     return (a * b) / __gcd(a, b);
  112. }
  113.  
  114. int bpow(int a, int n)
  115. {
  116.     int res = 1;
  117.     a %= MOD;
  118.     while (n > 0)
  119.     {
  120.         if (n & 1)
  121.         {
  122.             res *= a;
  123.             res %= MOD;
  124.         }
  125.  
  126.         a *= a;
  127.         a %= MOD;
  128.         n >>= 1;
  129.     }
  130.     return res;
  131. }
  132.  
  133. bool isPrime(int n)
  134. {
  135.     if (n < 2)
  136.     {
  137.         return false;
  138.     }
  139.  
  140.     for (int i = 2; i * i <= n; i++)
  141.     {
  142.         if (n % i == 0)
  143.         {
  144.             return false;
  145.         }
  146.     }
  147.  
  148.     return true;
  149. }
  150. /*======================SOME USEFUL FUNCTIONS END=======================*/
  151.  
  152. void brute()
  153. {
  154.     vector<int> prob(1005, 0);
  155.     int n, m;
  156.     cin >> n >> m;
  157.     vector<int> s(m);
  158.     for (int i = 0; i < n; i++)
  159.     {
  160.         int a, b;
  161.         cin >> a >> b;
  162.         for (int j = a; j <= b; j++)
  163.         {
  164.             prob[j]++;
  165.         }
  166.     }
  167.     for (auto &x : s)
  168.     {
  169.         cin >> x;
  170.     }
  171.     vector<int> ans;
  172.     for (int i = 0; i < m; i++)
  173.     {
  174.         int diff = 1e18, p = 0;
  175.         for (int j = 1; j <= 1000; j++)
  176.         {
  177.             if (prob[j] != 0)
  178.             {
  179.                 if (abs(j - s[i]) < diff)
  180.                 {
  181.                     diff = abs(j - s[i]);
  182.                     p = j;
  183.                 }
  184.             }
  185.         }
  186.  
  187.         ans.push_back(p);
  188.         prob[p] = 0;
  189.     }
  190.  
  191.     for (auto x : ans)
  192.     {
  193.         cout << x << " ";
  194.     }
  195.     cout << "\n";
  196. }
  197.  
  198. void solve()
  199. {
  200.     int n, m;
  201.     cin >> n >> m;
  202.     vector<int> S(m), ans;
  203.     map<int, int> mp;
  204.     for (int i = 0; i < n; i++)
  205.     {
  206.         int a, b;
  207.         cin >> a >> b;
  208.         mp[a] = b;
  209.     }
  210.     for (auto &s : S)
  211.     {
  212.         cin >> s;
  213.     }
  214.  
  215.     for (int s : S)
  216.     {
  217.         if (mp.upper_bound(s) == mp.begin())
  218.         {
  219.             // if all problems are more difficult than S
  220.             auto p = *mp.begin();
  221.             ans.push_back(p.fi);
  222.             mp.erase(p.fi);
  223.             if (p.fi + 1 <= p.se)
  224.             {
  225.                 mp.insert({p.fi + 1, p.se});
  226.             }
  227.         }
  228.         else
  229.         {
  230.             auto kth = mp.upper_bound(s);
  231.             auto previous = prev(kth);
  232.             auto p = *previous;
  233.             /*
  234.             l<=s<=r or r < s
  235.             */
  236.             if (p.fi <= s and s <= p.se)
  237.             {
  238.                 // l<= s <=r
  239.                 ans.push_back(s);
  240.                 if (s - 1 >= p.fi)
  241.                 {
  242.                     mp[p.fi] = s - 1;
  243.                 }
  244.                 else
  245.                 {
  246.                     mp.erase(p.fi);
  247.                 }
  248.  
  249.                 if (s + 1 <= p.se)
  250.                 {
  251.                     mp[s + 1] = p.se;
  252.                 }
  253.                 else
  254.                 {
  255.                     if (mp.count(s + 1))
  256.                     {
  257.                         mp.erase(s + 1);
  258.                     }
  259.                 }
  260.             }
  261.             else
  262.             {
  263.                 // r < s < l(next)
  264.                 if (kth != mp.end())
  265.                 {
  266.                     // if s is the most difficult problem now
  267.                     auto next = *kth;
  268.                     if (abs(s - p.se) <= abs(s - next.fi))
  269.                     {
  270.                         ans.push_back(p.se);
  271.                         if (p.se - 1 >= p.fi)
  272.                         {
  273.                             mp[p.fi] = p.se - 1;
  274.                         }
  275.                         else
  276.                         {
  277.                             mp.erase(p.fi);
  278.                         }
  279.                     }
  280.                     else
  281.                     {
  282.                         ans.push_back(next.fi);
  283.                         mp.erase(next.fi);
  284.                         if (next.fi + 1 <= next.se)
  285.                         {
  286.                             mp.insert({next.fi + 1, next.se});
  287.                         }
  288.                     }
  289.                 }
  290.                 else
  291.                 {
  292.                     ans.push_back(p.se);
  293.                     if (p.se - 1 >= p.fi)
  294.                     {
  295.                         mp[p.fi] = p.se - 1;
  296.                     }
  297.                     else
  298.                     {
  299.                         mp.erase(p.fi);
  300.                     }
  301.                 }
  302.             }
  303.         }
  304.     }
  305.  
  306.     for (auto x : ans)
  307.     {
  308.         cout << x << " ";
  309.     }
  310.     cout << "\n";
  311. }
  312.  
  313. signed main()
  314. {
  315.     // FIO;
  316.     Lightspeed;
  317.     //usaco("cowlands");
  318.     int TC = 1;
  319.     cin >> TC;
  320.     for (int tt = 1; tt <= TC; tt++)
  321.     {
  322.         google;
  323.         solve();
  324.     }
  325.  
  326.     return 0;
  327. }
  328.  
  329. /* stuff you should look for
  330.     * int overflow, array bounds
  331.     * special cases (n=1?)
  332.     * do smth instead of nothing and stay organized
  333.     * WRITE STUFF DOWN
  334. */
  335.  
RAW Paste Data