競技プログラミング用 知識集積所
ABC403C - 403 Forbidden
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
単純にやると、N×Mのbool型二次元配列を用意することになるが、NやMの値が大きくてTLEしてしまう。
そこで、権限がないものについてはわざわざデータを用意せず、「権限があるという情報がなければ権限がないと判断する」という方針を取ることで高速化する。
そこで、権限がないものについてはわざわざデータを用意せず、「権限があるという情報がなければ権限がないと判断する」という方針を取ることで高速化する。
権限があるものだけを管理するには、飛び飛びの値を管理するのが得意なmapやsetなどを用いるのがよい。
今回は同じ人に複数の権限が与えられる可能性があるので、mapでは難しい。
vector<set<int>>かset<pair<int,int>>を使うのがよい。
今回は同じ人に複数の権限が与えられる可能性があるので、mapでは難しい。
vector<set<int>>かset<pair<int,int>>を使うのがよい。
クエリ2で全体権限を与える場合に、個別ページ全部に権限を与えていくと、クエリ2を連打される最悪の入力に対してQ×Mの処理時間がかかってTLEする。
全体権限は全体権限として管理し、クエリ3のときに「個別ページ権限か全体権限があればOK」と判断する。
全体権限は全体権限として管理し、クエリ3のときに「個別ページ権限か全体権限があればOK」と判断する。
