Submission #69885061

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  /////////////////// 前入力 ///////////////////
  
  int n, q;
  cin >> n >> q;

  /////////////////// 前処理 ///////////////////

  // どのバージョンのマシンが何台あるかを管理するpriority_queue
  // (バージョン番号,台数)で持って、小さい方から取り出す
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
  for (int i=1; i<=n; i++) {
    que.emplace(i,1);
  }

  // 番兵を入れておく
  que.emplace(1e9,1);

  /////////////////// ループ ///////////////////

  for (int loop=0; loop<q; loop++) {
    
    //////////////////// 入力 ////////////////////

    int x , y;
    cin >> x >> y;

    //////////////// 出力変数定義 ////////////////

    int result = 0;

    //////////////////// 処理 ////////////////////

    // バージョンが小さい台数を数える
    while (que.top().first<=x) {
      result += que.top().second;
      que.pop();
    }

    // 新たにバージョンyのものがresult台できる
    que.emplace(y,result);

    //////////////////// 出力 ////////////////////

    cout << result << endl;
    
  }

  /////////////////// 後処理 ///////////////////



  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result