D - Double Landscape

[Q] https://atcoder.jp/contests/keyence2019/tasks/keyence2019_d

BITで80msくらい。1度ACすると効率化できるのがわかる。でもバグりそう。
0.  A[] も B[] も順番関係ないので、sortしておくと考えやすいかも。
1. 一番大きい数 N*M から盤面に入れていくことを考える。1まで探索。
次の4通りで場合分け。
2. 盤面に入れる数字 x を、N*M ~ 1 まで探索していく。もしxがAに2つ以上あれば実現不可能なので0。Bに2つ以上あっても0。
2. xがAとBどちらにもあったら、確定置き1マス。
2. xがAだけにあったら、x以上のBならどこでもおける。
2. xがBだけにあったら、x以上のAならどこでもおける。
2. xがAにもBにもなかったら、x以上のA * B ならどこでも置ける。

Q. 例
3 3
5 7 9
6 8 9

0. sortする
  6 8 9
5
7
9

1. N*M = 9 から埋めていくことを考える。
答えの初期値は 1通り
ans = 1

2) 9 を入れる
used = 0 // 置いたマス数を数えておく

A にも B にも 9 があるので、(2,2)に確定入れ。
  6 8 9
5
7
9    [9]

選択の余地は 1通り しかない。
ans *= 1 // 1
used = 1

2) 8 を入れる
A に指定があるので、Bのおける範囲を考える。
8以上のBは{9}で1要素。結果(2,1)しかおけない
  6 8 9
5
7
9   x 9
ans *= 1 //1
used = 2

2) 7 を入れる
B に指定があるので、A のおける範囲を考える。
7以上のAは、{8,9}で2要素。(1,1)と(1,2)における。
  6 8 9
5
7   x x
9   8 9
選択の余地は 2通り なので
ans *= 2 // 2
used = 3

2) 6 を入れる。
A に指定があるので、B のおける範囲を考える。
6 以上の B は{7,9}で2要素。
  6 8 9
5
7 x   7
9 x 8 9
x の2通りにおけるので、
ans *= 2 // 4
used = 4

2) 5 を入れる。
B に指定があるので、A のおける範囲を考える。
5以上のAは {6, 8, 9} で3要素。
  6 8 9
5 x x x
7     7
9 6 8 9
3 箇所に入るので、
ans *= 3 // 12
used = 5

2) 4 を入れる。
A にも B にもない。
ということは、4以上であればどこでも入れていい。

  6 8 9
5 5 x x
7 x x 7
9 6 8 9
4以上のAは{6,8,9} で3要素
4以上のBは{5,7,9} で3要素
ここまでで used = 5 で5マス使っているので、3*3 - 5 = 9 - 5 = 4マスなら自由に選べる。
ans *= 4 // 48
used = 6

2) 3 を入れる。
  6 8 9
5 5 4 x
7 x x 7
9 6 8 9
3マス入れられるので * 3

以降同じ。

ans = 48 * 3 * 2 * 1だと思う。

実装

vector<ll> A[1000010];
vector<ll> B[1000010];
ll N, M;
int main(){
 cincout();
 
 cin >> N >> M;
 Bit<1000010> yoko, tate; //1000*1000まで
 rep(i, N){
   ll a;
   cin >> a;
   yoko.add(a, 1);
   A[a].push_back(i);
 }
 rep(i, M){
   ll b;
   cin >> b;
   tate.add(b, 1);
   B[b].push_back(i);
 }
 mint ans=1;
 ll cnt=0; // 使った数
 // 大きい数からうめてく
 for(ll i=N*M; i>0; --i){
   ll asz = A[i].size();
   ll bsz = B[i].size();
   mint div = 0;
   ll all = yoko.rangesum(i, N*M+1) * tate.rangesum(i, N*M+1) - cnt;
   // 1. 最大値が 2個以上, はありえないので終了
   if (asz>1 || bsz>1){
     cout << 0 << endl;
     return 0;
   }
   // 1. AもBも指定なら確定1マス
   else if(asz==1 && bsz==1) div = 1;
   // 1. Aだけ指定なら、i以上のBマスならどこでもおける
   else if(asz==1 && bsz==0){
     div = tate.rangesum(i, N*M+1);
   }
   // 1. Bだけ指定なら、i以上のAマスならどこでもおける
   else if(asz==0 && bsz==1){
     div = yoko.rangesum(i, N*M+1);
   }
   // 1. 指定なしなら、i以上のマスならどこでもおける
   else if(asz==0 && bsz==0){
     div = max(all, 0LL);
   }
   ans *= div;
   ++cnt;
 }
 cout << ans << endl;
}

Q. バグ
A. N*M+1 とすべきところ、N*N+1 とか、 N+M*1 とか。永遠にタイポした。

https://atcoder.jp/contests/keyence2019/submissions/27493884