Submission #987188

#	Time	Username	Problem	Language	Result	Execution time	Memory
987188		Mohammadamin__Sh	Pinball (JOI14_pinball)	C++17	100 / 100	170 ms	29968 KiB

pinball

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 1e5 + 10, MOD = 1e9 + 7 ;
const ll INF = 1e16 + 100;

int m , n , a[maxn] , b[maxn] , c[maxn] , d[maxn];
vector<int> v;
pii tree[4*3*maxn];

void Update(int id , int L , int R , int idx , pii w){
	if(L+1 == R){
		tree[id] = {min(tree[id].F , w.F) , min(tree[id].S , w.S)};
		return;
	}
	int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
	if(idx < mid) Update(lc , L , mid , idx , w);
	else Update(rc , mid , R , idx , w);
	tree[id] = {min(tree[lc].F , tree[rc].F) , min(tree[lc].S , tree[rc].S)};
}

pii Get(int id , int L , int R , int l , int r){
	if(L == l and R == r) return tree[id];
	int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
	pii res1 = {INF,INF} , res2 = {INF,INF};
	if(l < mid) res1 = Get(lc , L , mid , l , min(r , mid));
	if(r > mid) res2 = Get(rc , mid , R , max(l , mid) , r);
	return {min(res1.F , res2.F) , min(res1.S , res2.S)};
}

int32_t main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	
	for(int i = 1 ; i < 12*maxn ; i++) tree[i] = {INF,INF};

	cin >> m >> n;
	for(int i = 1 ; i <= m ; i ++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		v.pb(a[i]) , v.pb(c[i]) , v.pb(b[i]); 
	}
	sort(all(v));
	if(v[0] > 1 or v.back() < n) return cout << -1 , 0;
	v.resize(unique(all(v)) - v.begin());
	n = v.size()-1;
	if(n == 0) return cout << 0 , 0;
	for(int i = 1 ; i <= m ; i++){
		a[i] = lower_bound(all(v) , a[i]) - v.begin();
		b[i] = lower_bound(all(v) , b[i]) - v.begin();
		c[i] = lower_bound(all(v) , c[i]) - v.begin();
	}
	int ans = INF;
	for(int i = 1 ; i <= m ; i++){
		pii w = Get(1 , 0 , n+1 , a[i] , b[i]+1);
		if(a[i] == 0) w.F = 0;
		if(b[i] == n) w.S = 0;
		if(w.F < INF and w.S < INF) ans = min(ans , w.F + w.S + d[i]);
		Update(1 , 0 , n+1 , c[i] , {w.F+d[i], w.S+d[i]});
	}
	cout << (ans == INF ? -1 : ans);
		
}

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