Educational Codeforces Round 112 (Rated for Div. 2) - E. Boring Segments

この問題を解説 AC しました。
全く考えもしなかった方針なので、とても面白いと感じました。

問題概要

個の区間が与えられる。 を被覆する区間の subset の最小コストを求めよ。
コスト: subset 中の 区間に与えられる の

考えたこと

1. DP かな〜。やっぱｗ。とりあえず でソートして、最小値を状態に持って、最大値の最小値として更新していくのをなんとか高速化したらできないかしら？→厳しそう
2. コストでにぶたんすると、使用する最小要素の を固定すると使える subset が一意に定まるので、これをなんとか間に合わせられないかしら？→厳しそう
考察の第一歩として、"とりあえず でソートするか！ｗ" をしてしまったために、 でソートを思いつけなくなってしまったのは良くないですね。

解法

まず でソートします。解法自体は "考えたこと2" に近くて、使用する subset の を固定すると、使用する subset の が大きくなるにつれて、条件を満たしやすくなります。単調性を発見したので、二分探索をしたいところですが、実装が厳しいので尺取りをします。
尺取りをする際には、区間 add, 区間 min 遅延セグ木を使うと実装が楽です。

提出コード

↓ac_library の展開を省いたコード

#include <bits/stdc++.h>

using namespace std;
#define rep(i,n) for(long long i=0;i<n;++i)
#define rep1(i,n) for(long long i=1;i<=n;++i)
#define rrep(i,n) for(long long i=n-1;i>=0;--i)
#define debug(output) if(debugFlag)cout<<#output<<"= "<<output<<endl
using lint = long long;
typedef pair<int,int> P;
const bool debugFlag=true;
const lint linf=1.1e18;const lint inf=1.01e9;
constexpr int MOD=1000000007;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
#include<atcoder/all>
using namespace atcoder;
int mn(int a,int b){return min(a,b);};
int e(){return inf;};
int op(int a,int b){return a+b;};
int id(){return 0;};
signed main(){
  int n,m;cin>>n>>m;
  vector<array<int,3>> a(n);
  rep(i,n)rep(j,3)cin>>a[i][(j+1)%3];
  sort(a.begin(),a.end());
  lazy_segtree<int,mn,e,int,op,op,id> tree(m+10);
  rep(i,m+10)tree.set(i,0);
  int res=inf;
  int r=0;
  rep(i,n){
    while(tree.prod(1,m)==0){
      if(r==n)break;
      tree.apply(a[r][1],a[r][2],1);
      ++r;
    }
    if(tree.prod(1,m)==0)continue;
    chmin(res,a[r-1][0]-a[i][0]);
    tree.apply(a[i][1],a[i][2],-1);
  }
  cout<<res<<"\n";
  return 0;
}