Advertisement
El_GEMMY

wrapping chocolate

Apr 5th, 2022
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.91 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 inf 2000000000
  22. #define nl '\n'
  23. #define ppcnt __builtin_popcount
  24. #define ppcntll __builtin_popcountll
  25. #define clz __builtin_clz
  26. #define clzll __builtin_clzll
  27. #define ctz __builtin_ctz
  28. #define ctzll __builtin_ctzll
  29. #define modulo(a, b, mod) ((((a) % mod) * ((b) % mod)) % mod)
  30. #define cnte(v, x) count(all(v), (x))
  31. #define mine(v) min_element(all(v))
  32. #define maxe(v) max_element(all(v))
  33. #define debug(x) cout << "x: " << x << nl;
  34. #define debug2(x, y) cout << "x: " << x << " y: " << y << nl;
  35. #define ordered_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
  36. #define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>
  37.  
  38. //vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
  39. //vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
  40.  
  41. template<typename T = int> istream& operator>>(istream& in, vector<pair<int, int>>& v){
  42.     for (auto& [x, y] : v) in >> x >> y;
  43.     return in;
  44. }
  45.  
  46. template<typename T = int> istream& operator>>(istream& in, vector<T>& v){
  47.     for (T& i : v) in >> i;
  48.     return in;
  49. }
  50.  
  51. template<typename T = int> ostream& operator<<(ostream& out, const vector<T>& v){
  52.     for (const T& x : v)
  53.         out << x << ' ';
  54.     return out;
  55. }
  56.  
  57. template<typename T = pair<int, int>> ostream& operator << (ostream& out, const vector<pair<int, int>>& v){
  58.     for(auto& [x, y] : v){
  59.         out << x << ' ' << y << nl;
  60.     }
  61.     return out;
  62. }
  63.  
  64. void Start_Crushing() {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.     cout.tie(nullptr);
  68. #ifndef ONLINE_JUDGE
  69.     freopen("input.txt", "r", stdin);
  70.     freopen("output.txt", "w", stdout);
  71. #endif
  72. }
  73.  
  74. struct item{
  75.     int x, y;
  76.     char type;
  77.  
  78.     item(){
  79.         x = y = 0;
  80.         type = '-';
  81.     }
  82.     item(int x, int y, char type){
  83.         this -> x = x;
  84.         this -> y = y;
  85.         this -> type = type;
  86.     }
  87. };
  88.  
  89. void solve(){
  90.     int n, m; cin >> n >> m;
  91.     vector<item> v;
  92.  
  93.     deque<int> tmp;
  94.     for(int i = 0; i < n; i++){
  95.         int entry; cin >> entry;
  96.         tmp.emplace_back(entry);
  97.     }
  98.  
  99.     for(int i = 0; i < n; i++){
  100.         int entry; cin >> entry;
  101.         v.emplace_back(item(tmp.front(), entry, 'c'));
  102.         tmp.pop_front();
  103.     }
  104.  
  105.     for(int i = 0; i < m; i++){
  106.         int entry; cin >> entry;
  107.         tmp.emplace_back(entry);
  108.     }
  109.  
  110.     for(int i = 0; i < m; i++){
  111.         int entry; cin >> entry;
  112.         v.emplace_back(item(tmp.front(), entry, 'b'));
  113.         tmp.pop_front();
  114.     }
  115.  
  116.     sort(all(v), [](item& a, item& b){
  117.         if(a.x == b.x){
  118.             return (a.type == 'b' and b.type == 'c');
  119.         }
  120.         return a.x > b.x;
  121.     });
  122.  
  123.  
  124.     multiset<pair<int, int>> st;
  125.  
  126.     for(item& i : v){
  127.         if(i.type == 'b'){
  128.             st.emplace(i.y, i.x);
  129.         }else{
  130.             auto pos = st.lower_bound({i.y, i.x});
  131.  
  132.             if(pos == st.end())
  133.                 return void(cout << "No");
  134.  
  135.             st.erase(st.find(*pos));
  136.         }
  137.     }
  138.     cout << "Yes";
  139. }
  140.  
  141. int main(){
  142.     Start_Crushing();
  143.  
  144.     int t = 1;
  145. //    /*Multiple test cases?*/ cin >> t;
  146.     while (t--) {
  147.         solve();
  148.         if(!t) break;
  149.         cout << nl;
  150.     }
  151.  
  152. //    for(int tc = 1; tc <= t; tc++){
  153. //        cout << "Case #" << tc << ": ";
  154. //        solve();
  155. //        if(tc != t)
  156. //            cout << nl;
  157. //    }
  158.  
  159.     return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement