https://pastein.ru/t/86
скопируйте уникальную ссылку для отправки
Загрузка данных
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iterator>
#include <string>
#include <iomanip>
//#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define all(v) v.begin(),v.end()
#define vpii vector <pair<int,int> >
#define CIN ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define Unique(x) x.erase(unique(all(x)), x.end())
#define Read() freopen("input.cpp", "r", stdin)
#define Write() freopen("output.cpp", "w", stdout)
#define FOR(q,w,e) for(q=w;q<e;q++)
#define endl "\n"
#define ll long long
int main()
{
int n,x,key,mid,lt,rt;
long long j = 0;
int konec,i;
ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL);
cin >> n >> x;
vector < pair < pair < int,long long > ,pair < int,int > > > b(n);
for(i = 0 ; i < n ; i ++ )
{
cin >> b[i].second.first >> b[i].second.second >> b[i].first.second;
b[i].first.first = b[i].second.second - b[i].second.first + 1;
}
sort(b.begin(),b.end());
if(x % 2 == 0) j = x / 2;
else j = x / 2 + 1;
if(b[0].first.first > j)
{
cout << - 1;
return 0;
}
j = 0;
key = 0;
vector < pair < pair < int,long long > ,pair < int,int > > > a (n);
vector < pair < pair < int,long long > ,pair < int,int > > > c (n);
for(i = 0 ; i < n && b[i].first.first < x ; i ++ )
{
while(i < n - 1 && b[i].first.second == b[i + 1].first.second && b[i].second.first == b[i + 1].second.first && b[i].second.second == b[i + 1].second.second)
{
i ++ ;
}
if(x % 2 != 0 || b[i].first.first != x / 2)
{
a[j].first.first = b[i].first.first;
a[j].first.second = b[i].first.second;
a[j].second.second = b[i].second.second;
a[j].second.first = b[i].second.first;
j ++ ;
}
else
{
c[key].first.first = b[i].first.first;
c[key].first.second = b[i].first.second;
c[key].second.second = b[i].second.second;
c[key].second.first = b[i].second.first;
key ++ ;
}
// cout << "i=" << i << " j=" << j << "\n";
}
// cout << "i=" << i << " j=" << j << "\n";
a.resize(j);
c.resize(key);
konec = j;
if(x % 2 == 0) j = x / 2;
if(a[a.size() - 1].first.first == x / 2) konec = a.size();
else
{
for(i = 0 ; i < a.size() ; i ++ )
{
if(a[i].first.first > j)
{
konec = i;
break;
}
}
}
/*
cout << "b= \n";
for(i = 0 ; i < n ; i ++ )
{
cout << b[i].first.first << " " << b[i].first.second << " " << b[i].second.first << " " << b[i].second.second << "\n";
}
cout << "a= \n";
for(i = 0 ; i < a.size() ; i ++ )
{
cout << a[i].first.first << " " << a[i].first.second << " " << a[i].second.first << " " << a[i].second.second << "\n";
}
cout << "c= \n";
for(i = 0 ; i < c.size() ; i ++ )
{
cout << c[i].first.first << " " << c[i].first.second << " " << c[i].second.first << " " << c[i].second.second << "\n";
}
cout << "konec=" << konec << "\n";
*/
long long f = 3e9;
for(i = 0 ; i < c.size() && c[i].first.second < f ; i ++ )
{
j = i + 1;
while(j < c.size() && f > c[j].first.second + c[i].first.second)
{
// cout << "j=" << j << " ";
if(c[i].second.second < c[j].second.first || c[i].second.first > c[j].second.second)
{
f = c[j].first.second + c[i].first.second;
break;
}
j ++ ;
}
// cout << "\n";
}
int oper;
for(i = 0 ; i < konec ; i ++ ) // ?? ????? ??? ?? konec
{
if(a[i].first.second < f)
{
if(a[i].first.first != a[i - 1].first.first)
{
// cout << i << " ";
j = i;
lt = j + 1;
rt = a.size() - 1;
key = x - a[j].first.first;
while(lt < rt && key < a[rt].first.first && key >= a[lt].first.first)
{
mid = (lt + rt) / 2 ;
if(key < a[mid].first.first)
{
rt = mid - 1;
}
else
{
if(key == a[mid].first.first)
{
rt = mid;
}
else
{
lt = mid + 1;
}
}
}
// cout << "rt=" << rt << "\n";
j = rt;
if(key == a[j].first.first)
{
// prover r and l
if(f > a[j].first.second + a[i].first.second && (a[j].second.second < a[i].second.first || a[j].second.first > a[i].second.second))
{
f = a[j].first.second + a[i].first.second;
// cout << "f=" << f << "\n";
}
while(j > 0 && a[j].first.first == a[j - 1].first.first)
{
j -- ;
}
oper = j;
// cout << "oper=" << oper << "\n";
while(a[j].first.first == key && j < a.size() && a[j].first.second + a[i].first.second < f)
{
if(a[i].second.second < a[j].second.first || a[i].second.first > a[j].second.second)
{
f = a[j].first.second + a[i].first.second;
break;
}
j ++ ;
}
}
}
else
{
j = oper;
while(a[j].first.first == key && j < a.size() && a[j].first.second + a[i].first.second < f)
{
if(a[i].second.second < a[j].second.first || a[i].second.first > a[j].second.second)
{
f = a[j].first.second + a[i].first.second;
break;
}
j ++ ;
}
}
}
}
if(f != 3e9)
{
cout << f;
}
else
{
cout << - 1;
}
/*
https: // codeforces.com / contest / 822 / submission / 66507075
4 3
1 1 2
1 1 3
2 3 3
2 3 4
*/
}