ABC113-C 「ID」

atcoder.jp

実装に工夫が必要な問題として認識されているようです。
実際、この問題を解くときに引っかかるポイントは
「県ごとに、市が誕生した順番を整理（座標圧縮）する必要がある」
という点です。
座標圧縮の方法としては

①値をset等で管理⇒sort⇒lower_bound等で値を探索し、イテレータを返す
②値をmapで管理⇒mapは辞書順ソートされるので、forループ等で取り出した順に番号をつけていく（ABC036-C「座圧」）
atcoder.jp

などの方法が考えられそうです。
①については、けんちょんさんの記事
（AtCoder ABC 113 C - ID (300 点) (座標圧縮の教育的練習問題) - けんちょんの競プロ精進記録）で取り上げられており、公式解説も同様です。
↓

int n, m;
int p[100000], y[100000];
vector<int> yd[100001];
int main()
{
    scanf("%d%d",&N,&M);
    rep(i, m) scanf("%d%d", &p[i], &y[i]), yd[p[i]].push_back(y[i]); 
    rep(i, n) sort(yd[i+1].begin(), yd[i+1].end());  //1<=p[i]<=n
    rep(i, m) printf("%012lld\n", ll(p[i])*1000000+int(lower_bound(yd[p[i]]. begin(), yd[p[i]].end(), y[i])-yd[p[i]].begin())+1);
    return 0;
}

②について、↓のコードのようにmapをvectorで持てば可能です（コードでは0埋めをしていません）。

int main()
{
    ll n,m;
    cin >> n >> m;
    vector<ll> y(m);
    vector<ll> p(m);
    vector<map<ll,ll>> q(n+1);
    rep(i,m){
        cin >> p[i] >> y[i];
        q[p[i]][y[i]]=0;
    }
    rep(i,m){
        ll j=1;
        for(auto x:q[p[i]]){
            q[p[i]][x.first]=j;
            j++;
        }
    }
    rep(i,m){
        cout << p[i] << q[p[i]][y[i]] << endl;
    }
    return 0;
}