526互联

[ARC147E] Examination

发布时间 2023-03-23 17:09:05作者: DCH233

[ARC147E] Examination

发现题解区和我做法都不一样，那就写一下吧。

首先判合法很显然把 \(A\) 和 \(B\) 都排序后依次比较即可。

首先转化成求最小的可以交换的集合。不难发现所有 \(B_i > A_i\) 的人都必须在这个集合内。接下来剩下的怎么取。

感觉很贪心，那么就按 \(B\) 从小到大遍历上述的人，考虑如何满足当前限制。注意到如果不使用其它人的 \(A\)，那么我们只能使用还未使用的 \(A\) 中的最小值，所以考虑维护当前可用的 \(A\)。

如果此时最小的 \(A\) 无法满足限制，那么我们应该怎么办呢？肯定是用这个 \(A\) 去满足另外一些点的 \(B\)，然后用这样的人对应的 \(A\) 来更新当前可用 \(A\) 的集合，不难发现一定会选可选的人中 \(A\) 最大的人。直到最小的可用的 \(A\) 能满足当前 \(B\) 的限制。

所以我们要做的就是：维护可用的 \(A\) 集合和最小值，并且查找 \(B\) 在某个范围内的 \(A\) 的最大值。前者可以用一个 std::multiset，后者可以写一个支持查询区间最大值和单点修改的线段树。复杂度就是 \(O(n \log n)\)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

namespace IO {
  #define isdigit(x) (x >= '0' && x <= '9')
  template<typename T>
  inline void read(T &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if(f) x = -x;
  }
  template<typename T>
  inline void write(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  #undef isdigit
}
using namespace IO;

const int N = 3e5 + 10;

int n;
struct Score {
  int a, b;
  inline bool operator < (Score y) const {
    return b < y.b;
  }
}a[N];

multiset<int> s;

struct SegmentTree {
  #define lc (k << 1)
  #define rc (k << 1 | 1)
  #define mid (l + r >> 1)
  int tr[N << 2];
  inline void modify(int k, int l, int r, int pos) {
    if(l > pos || r < pos) return;
    if(l == r) return tr[k] = l, void();
    modify(lc, l, mid, pos), modify(rc, mid + 1, r, pos);
    tr[k] = a[tr[lc]].a > a[tr[rc]].a ? tr[lc] : tr[rc];
    return;
  }
  inline int query(int k, int l, int r, int L, int R) {
    if(r < L || R < l) return 0;
    if(L <= l && r <= R) return tr[k];
    int x = query(lc, l, mid, L, R), y = query(rc, mid + 1, r, L, R);
    if(a[x].a > a[y].a) return x;
    return y;
  }
}seg;

inline int find(int x) {
  int k = lower_bound(a + 1, a + n + 1, (Score){0, x + 1}) - a - 1;
  return seg.query(1, 1, n, 1, k);
}

int tmp1[N], tmp2[N];

int main() {
  read(n);
  for(int i = 1; i <= n; ++i)
    read(a[i].a), read(a[i].b), tmp1[i] = a[i].a, tmp2[i] = a[i].b;
  
  sort(tmp1 + 1, tmp1 + n + 1),
  sort(tmp2 + 1, tmp2 + n + 1);
  for(int i = 1; i <= n; ++i)
    if(tmp1[i] < tmp2[i]) {
      puts("-1");
      return 0;
    }

  sort(a + 1, a + n + 1, [](Score x, Score y) {
    return x.b < y.b;
  });

  int ans = 0;
  for(int i = 1; i <= n; ++i) {
    if(a[i].b > a[i].a) {
      ++ans, s.insert(a[i].a);
      a[i].a = -1;
    }
    seg.modify(1, 1, n, i);
  }

  for(int i = 1; i <= n; ++i) {
    if(a[i].b > a[i].a) {
      int x = *s.begin();
      while(x < a[i].b) {
        s.erase(s.begin());
        int p = find(x);
        s.insert(a[p].a);
        a[p].a = -1;
        seg.modify(1, 1, n, p);
        ++ans;
        x = *s.begin();
      }
      s.erase(s.begin());
    }
  } 
  printf("%d\n", n - ans);
  return 0;
}