CODE FESTIVAL 2016 Grand Final: A - 1D Matching

,

https://beta.atcoder.jp/contests/cf16-exhibition-final/tasks/cf16_exhibition_final_a

まあはいだけどなんだか解説が書きにくかった。

solution

まだ使ってないものの数を数えながら座標の小さい方から順に見ていく。$O(N \log N)$。

implementation

#include <algorithm>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;
int main() {
// input
int n; scanf("%d", &n);
vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
vector<int> b(n); repeat (i, n) scanf("%d", &b[i]);
// solve
vector<pair<int, bool> > events;
repeat (i, n) {
events.emplace_back(a[i], false);
events.emplace_back(b[i], true);
}
sort(whole(events));
ll result = 1;
int cnt = 0;
for (auto event : events) {
int delta = (event.second ? 1 : -1);
if (cnt != 0 and (cnt > 0) != event.second) {
result = (result * std::abs(cnt)) % mod;
}
cnt += delta;
}
// output
printf("%lld\n", result);
return 0;
}