接上一篇文章;

这里直接把左端点和右端点映射到vector数组上;

映射一个open和close数组;

枚举1..2e5

如果open[i]内有安排;

则用那个安排和dp数组来更新答案;

更新答案完之后,如果有close数组

则把close数组里面的安排用来更新dp数组;

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define ms(x,y) memset(x,y,sizeof x)#define Open() freopen("F:\\rush.txt","r",stdin)#define Close() ios::sync_with_stdio(0)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = {
    0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {
    0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 2e5;const int INF = 2e9+10;struct abc{    int l,r,cost;};int n,x,dp[N],ans = INF;vector 
        
          open[N+100],close[N+100];int main(){    //Open();    Close();    cin >> n >> x;    abc temp;    rep1(i,1,n){        cin >> temp.l >> temp.r >> temp.cost;        open[temp.l].pb(temp);        close[temp.r].pb(temp);    }    int len;    rep1(i,1,N){        while (!open[i].empty()){            temp = open[i].back();            open[i].pop_back();            len = temp.r-temp.l+1;            if (x>=len){                if (dp[x-len] > 0)                    ans = min(ans,dp[x-len]+temp.cost);            }        }        while (!close[i].empty()){            temp = close[i].back();            close[i].pop_back();            len = temp.r-temp.l+1;            if (dp[len]==0)                dp[len] = temp.cost;            else                dp[len] = min(dp[len],temp.cost);        }    }    if (ans==INF)        cout << -1 << endl;    else        cout << ans << endl;    return 0;}