Submission #16447815

---

Source Code Expand

#include<bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (ll i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT
#define chmax(x, a)  do { x = max(x, a); } while(0)
#define chmin(x, a)  do { x = min(x, a); } while(0)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll,ll> PLL;


void solve() {
  ll H, W;
  cin >> H >> W;
  vector<ll> a(H), b(H);
  map<ll,ll> m;
  multiset<ll> s;
  rep(x, W) {
    m[x] = x;
    s.insert(0);
  }
  rep(i, H) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  rep(i, H) {
    auto it = m.lower_bound(a[i]);
    // 削除対象のx一覧
    vector<ll> dels; 
    while (it != m.end() && it->first <= b[i]+1) {
      dels.push_back(it->first);
      it++;
    }
    // 削除
    ll mx = -1;
    for (auto x : dels) {
      chmax(mx, m[x]);
      s.erase(s.find(x-m[x]));
      m.erase(m.find(x));
      //cout << "delete x=" << x << endl;
    }
    // 追加
    if (mx != -1 && b[i] + 1 < W) {
      m[b[i]+1] = mx;
      s.insert(b[i]+1 - mx);
      //cout << "add x=" << b[i]+1 << endl;
    }
    // 答え
    ll ans = -1;
    if (s.size() > 0)
      ans = i + 1 + *s.begin();
    cout << ans << endl;
  }
}

int main() {
  //ll T;
  //cin >> T;
  //rep(_,T)
    solve();
  return 0;
}

Submission Info

Judge Result