A. Berstagram

1400
  • Quiz
  • AC
  • 問題解説
    • 1番目に1番の投稿、2番目に2番の投稿、... と最初なっている
    • 各投稿に「いいね」が付くと、その投稿は1つ上の表示になる
    • M個のLikeの処理後、各投稿の位置の最小値と最大値を答えよ
  • 解法
    • 普通の配列はA[i] = 123; のようにindex => valという対応を持っているが、valからindexを逆引きできる配列も用意しておく
    • あとは普通に実装するのみ（difficulty 1400ないだろ...）
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M; 
    cin>>N>>M;

    VI A(N);
    VI I(N); // val to index
    VI MA(N); // max
    VI MI(N); // min
    rep(i,N){
      A[i]=i;
      I[i]=i;
      MA[i]=i;
      MI[i]=i;
    }

    while(M--){
      ll a;cin>>a;
      a--;

      ll idx=I[a];
      if(idx==0){
        // 移動は発生しない
      }else{
        // 1つ上に上がる
        ll b = A[idx-1];
        A[idx-1] = a;
        A[idx] = b;

        I[a] = idx-1;
        chmax(MA[a], idx-1);
        chmin(MI[a], idx-1);

        I[b] = idx;
        chmax(MA[b], idx);
        chmin(MI[b], idx);
      }
    }
    rep(i,N){
      ll ma = MA[i]+1;
      ll mi = MI[i]+1;
      p2(mi,ma);
    }
    return 0;
}