#1195589 (C++23(gcc16)) No.2543 Many Meetings

• 問題: No.2543 Many Meetings
• ユーザー: C
• 提出日時: 2026-10-27 20:56:12
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 67 ms / 2,000 ms
• コード長: 3,748 bytes
• コンパイル時間: 8,738 ms
• コンパイル使用メモリ: 395,808 KB
• 実行使用メモリ: 37,632 KB
• 最終ジャッジ日時: 2026-10-27 20:56:28
• 合計ジャッジ時間: 13,922 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge7_0

ファイルパターン	結果
sample	AC * 3
other	AC * 41

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
// using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

#line 2 "misc/doubling.hpp"

template <typename T>
struct BinaryLifting {
  using Data = pair<int, T>;

  const int N, LOG;
  vector<vector<Data>> table;
  T I;

  BinaryLifting(int n, uint64_t lim, const T I_ = T())
      : N(n), LOG(__lg(max<uint64_t>(lim, 1)) + 2), I(I_) {
    table.resize(LOG, vector<Data>(n, Data(-1, I)));
  }

  void set_next(int k, int nxt, const T& t) { table[0][k] = Data(nxt, t); }

  void build() {
    for (int k = 0; k + 1 < LOG; ++k)
      for (int i = 0; i < N; ++i) {
        int pre = table[k][i].first;
        if (pre == -1) {
          table[k + 1][i] = table[k][i];
        } else {
          table[k + 1][i].first = table[k][pre].first;
          table[k + 1][i].second = table[k][i].second + table[k][pre].second;
        }
      }
  }

  // i から t 回進んだ先, (地点, モノイド和) を返す
  Data query(int i, uint64_t t) const {
    T d = I;
    for (int k = LOG - 1; k >= 0; k--) {
      if ((t >> k) & 1) {
        d = d + table[k][i].second;
        i = table[k][i].first;
      }
      if (i == -1) break;
    }
    return Data(i, d);
  }

  // query(i, pow(2, k))
  inline Data query_pow(int i, int k) const { return table[k][i]; }

  // assuming graph is DAG ( edge(u, v) <-> u < v )
  // find max j | j <= t, path from i to j exists
  inline pair<uint64_t, Data> binary_search(int i, int t) {
    int thres = i;
    T d = I;
    uint64_t times = 0;
    for (int k = LOG - 1; k >= 0; k--) {
      int nxt = table[k][thres].first;
      if (nxt != -1 && nxt <= t) {
        d = d + table[k][thres].second;
        thres = nxt;
        times += 1LL << k;
      }
    }
    return make_pair(times, Data(thres, d));
  }

  // assuming graph is DAG ( edge(u, v) <-> u < v )
  // find min j | j >= t, path from i to j exists
  inline pair<uint64_t, Data> binary_search2(int i, int t) {
    int thres = i;
    T d = I;
    uint64_t times = 0;
    for (int k = LOG - 1; k >= 0; k--) {
      int nxt = table[k][thres].first;
      if (nxt != -1 && nxt >= t) {
        d = d + table[k][thres].second;
        thres = nxt;
        times += 1LL << k;
      }
    }
    return make_pair(times, Data(thres, d));
  }
};

template <typename T>
using Doubling = BinaryLifting<T>;

/**
 * @brief Binary Lifting(ダブリング)
 * @docs docs/misc/doubling.md
 */

int main()
{
  	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<pi>meetings(N);
	for(auto& [l,r]:meetings)cin>>l>>r;
	sort(all(meetings));
	vi start(N);
	rep(i,0,N)start[i]=meetings[i].first;
	vi suffmn(N+1,-1);
	rrep(i,0,N){
		suffmn[i]=suffmn[i+1];
		if(suffmn[i]==-1||meetings[i].second<meetings[suffmn[i]].second){
			suffmn[i]=i;
		}
	}
	Doubling<int>D(N,K-1);
	rep(i,0,N){
		int pos=lower_bound(all(start),meetings[i].second)-start.begin();
		if(pos<N)D.set_next(i,suffmn[pos],0);
	}
	D.build();
	int ans=INT_MAX;
	rep(i,0,N){
		int last=D.query(i,K-1).first;
		if(last!=-1)ans=min(ans,meetings[last].second-meetings[i].first);
	}
	if(ans==INT_MAX)cout<<-1<<'\n';
	else cout<<ans<<'\n';
}