Advertisement
pb_jiang

CF555b WA

Sep 22nd, 2022 (edited)
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
  5. template <typename... Args> void logger(string vars, Args &&...values)
  6. {
  7.     cerr << vars << " = ";
  8.     string delim = "";
  9.     (..., (cerr << delim << values, delim = ", "));
  10.     cerr << endl;
  11. }
  12.  
  13. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  14. using ll = long long;
  15. using pii = pair<int, int>;
  16. using pll = pair<ll, ll>;
  17. using plli = pair<pll, int>;
  18.  
  19. int n, m;
  20. pll rng[200003];
  21. plli srng[200003];
  22. int main(int argc, char **argv)
  23. {
  24.     scanf("%d%d", &n, &m);
  25.     for (int i = 1; i <= n; ++i)
  26.         scanf("%lld%lld", &rng[i].first, &rng[i].second);
  27.     for (int i = 1; i < n; ++i)
  28.         srng[i].first.first = rng[i + 1].first - rng[i].second, srng[i].first.second = rng[i + 1].second - rng[i].first,
  29.         srng[i].second = i;
  30.     sort(srng + 1, srng + n);
  31.     pll a;
  32.     mpq<pll> pq;
  33.     for (int i = 1; i <= m; ++i)
  34.         scanf("%lld", &a.first), a.second = i, pq.push(a);
  35.     bool succ = true;
  36.     vector<int> ans(n);
  37.     for (int i = 1; i < n; ++i) {
  38.         const auto &bg = srng[i];
  39.         dbg(bg.first.first, bg.first.second, bg.second);
  40.         if (pq.empty()) {
  41.             succ = false;
  42.             goto fail;
  43.         }
  44.         auto h = pq.top();
  45.         dbg(h.first, h.second);
  46.         pq.pop();
  47.     test:
  48.         if (h.first > bg.first.second) {
  49.             succ = false;
  50.             goto fail;
  51.         }
  52.         if (h.first < bg.first.first) {
  53.             if (pq.empty()) {
  54.                 succ = false;
  55.                 goto fail;
  56.             } else {
  57.                 h = pq.top();
  58.                 dbg(h.first, h.second);
  59.                 pq.pop();
  60.                 goto test;
  61.             }
  62.         }
  63.         ans[bg.second] = h.second;
  64.     }
  65. fail:
  66.     if (succ) {
  67.         printf("Yes\n");
  68.         for (int i = 1; i < ans.size(); ++i) {
  69.             printf("%d ", ans[i]);
  70.         }
  71.         printf("\n");
  72.     } else {
  73.         printf("No\n");
  74.     }
  75.     return 0;
  76. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement