【AtCoder】setやmapを使う際の注意点

ポイント

• lower_boundについて、vectorに対してはstd::lower_boundを使い、set/mapに対してはstd::set::lower_bound/std:: map::lower_boundを使う
• std::distanceは、vectorに対して使う場合はO(1)であるが、setやmapに対して使う場合はO(N)になってしまうので注意

例題

ABC213C - Reorder Cards

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define all(a) (a).begin(), (a).end()

int main() {
  int H, W, N; cin >> H >> W >> N;
  set<int> tmpr, tmpc;
  vector<P> A(N);
  for (int i = 0; i < N; ++i) {
    int x, y; cin >> x >> y;
    x--; y--;
    tmpr.insert(x);
    tmpc.insert(y);
    A[i] = P(x, y);
  }
  
  // setをvectorに変換
  vector<int> row(all(tmpr)), col(all(tmpc));
  for (auto [x, y] : A) {
    int r = distance(row.begin(), lower_bound(all(row), x));
    int c = distance(col.begin(), lower_bound(all(col), y));
    printf("%d %d\n", r+1, c+1);
  }
}