Submission #934948

#	Time	Username	Problem	Language	Result	Execution time	Memory
934948		vjudge1	Pinball (JOI14_pinball)	C++17	100 / 100	372 ms	29724 KiB

pinball

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <array>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);

ll Sum(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a += b;
 return a % MOD;
}

ll Mul(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a *= b;
 return a % MOD;
}

ll Pow(ll a , ll b , ll MOD)
{
   ll res = 1;
   while(b)
   {
        if((b & 1))res = Mul(res , a , MOD);
     a = Mul(a , a , MOD);
     b >>= 1;
   }
   return res;
}

ll Min(ll a , ll b)
{
   if(a > b)return b;
   return a;
}

ll Max(ll a , ll b)
{
   if(a > b)return a;
   return b;
}

ll Ceil(ll a , ll b)
{
 if(b < 0)
  a *= -1, b *= -1;

 if(a < 0)return a/b;

 return(a + (b-1))/b;
}

/////////////////////
//VALS
const int maxn = 1e5;
const int INF = (1 << 19);
int lft[maxn + 10];
int rgt[maxn + 10];
int mid[maxn + 10];
int cost[maxn + 10];
ll dp[maxn + 10][2];
ll tri[2 * INF];
map<int, int>con;

/////////////////////
//FUNS
void reset() {
	for(int i = 0; i < 2 * INF; i++) {
		tri[i] = 1e18;
	}
}
void upd(int v, ll x) {
	v += INF;
	while(v > 0) {
		tri[v] = min(tri[v], x);
		v /= 2;
	}
}
ll que(int l, int r) {
	l += INF;
	r += INF;
	ll ans = 1e18;
	while(l <= r) {
		if(l & 1) {
			ans = min(ans, tri[l]);
		}
		if(!(r & 1)) {
			ans = min(ans, tri[r]);
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
/////////////////////
//SOLVE
void solve()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> lft[i] >> rgt[i] >> mid[i] >> cost[i];
		con[lft[i]] = 0;
		con[rgt[i]] = 0;
		con[mid[i]] = 0;
	}
	con[1] = 0;
	con[m] = 0;
	int k = 1;
	for(auto x : con) {
		con[x.F] = k++;
	}
	reset();
	upd(1, 0);
	for(int i = 1; i <= n; i++) {
		dp[i][0] = que(con[lft[i]], con[rgt[i]]) + cost[i];
		upd(con[mid[i]], dp[i][0]);
	}
	reset();
	upd(con.size(), 0);
	for(int i = 1; i <= n; i++) {
		dp[i][1] = que(con[lft[i]], con[rgt[i]]) + cost[i];
		upd(con[mid[i]], dp[i][1]);
	}
	ll ans = 1e18;
	for(int i = 1; i <= n; i++) {
		//cout << dp[i][0] << ' ' << dp[i][1] << '\n';
		ans = min(ans, dp[i][0] + dp[i][1] - cost[i]);
	}
	if(ans == 1e18) {
		cout << -1 << '\n';
	}
	else {
		cout << ans << '\n';
	}

}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49