Submission #855186

#	Time	Username	Problem	Language	Result	Execution time	Memory
855186		ooscode	Pinball (JOI14_pinball)	C++17	100 / 100	306 ms	35172 KiB

pinball

// IN THE NAME OF ALLAH
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define int ll
#define kids int tm = (tl + tr)>>1; int cl = v<<1; int cr = v<<1|1
#define test int n; cin >> n; while(n--)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
 
const int N = 3e5 + 10;
const int K = 2e3+10;
const ll mod = 1e9+7;
const ll INF = 1e18+10;
const int P = 31;
const int lg = 25;

int n;

struct segment {
	int st[N << 2];

	void init(int v , int tl , int tr) {
		st[v] = INF;
		if(tl == tr) 	
			return;

		kids;
		init(cl , tl , tm);
		init(cr , tm+1 , tr);
	}

	void upd(int v , int tl , int tr , int pos , int x) {
		if(tl == tr) {
			st[v] = min(st[v] , x);
			return;
		}

		kids;
		if(pos <= tm)
			upd(cl , tl , tm , pos , x);
		else	
			upd(cr , tm+1 , tr , pos , x);

		st[v] = min(st[cl] , st[cr]);
	}

	int ask(int v , int tl , int tr , int l , int r) {
		if(tl == l && tr == r)
			return st[v];
		if(l > r)
			return INF;
		kids;
		// cout << v << " " << min(ask(cl , tl , tm , l , min(tm , r)) , ask(cr , tm+1 , tr , max(l , tm+1) , r)) << "\n"; 
		return min(ask(cl , tl , tm , l , min(tm , r)) , ask(cr , tm+1 , tr , max(l , tm+1) , r));
	}
} seg , ges;

int a[N] , b[N] , c[N] , d[N];

void solve() {
	vector<int> vec;
	int n , m;
	cin >> n >> m;

	for(int i = 1 ; i <= n ; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		vec.pb(a[i]); vec.pb(b[i]); vec.pb(c[i]);
	}

	vec.pb(1); vec.pb(m);

	sort(all(vec)); vec.resize(unique(all(vec)) - vec.begin());

	m = vec.size();

	seg.init(1 , 1 , m); ges.init(1 , 1 , m);
	seg.upd(1 , 1 , m , 1 , 0);
	ges.upd(1 , 1 , m , m , 0);

	int ans = INF;

	for(int i = 1 ; i <= n ; i++) {
		int x = seg.ask(1 , 1 , m , lower_bound(all(vec) , a[i]) - vec.begin() + 1 , lower_bound(all(vec) , b[i]) - vec.begin() + 1);
		seg.upd(1 , 1 , m , lower_bound(all(vec) , c[i]) - vec.begin() + 1 , x+d[i]);

		int y = ges.ask(1 , 1 , m , lower_bound(all(vec) , a[i]) - vec.begin() + 1 , lower_bound(all(vec) , b[i]) - vec.begin() + 1);
		ges.upd(1 , 1 , m , lower_bound(all(vec) , c[i]) - vec.begin() + 1 , y+d[i]);

		ans = min(ans , x + y + d[i]);
	}

	if(ans >= INF) {
		cout << "-1\n";
		return;
	}

	cout << ans << "\n";
}

signed main()
{   
	solve();
} 

// IT'S EASY TO SEE
// CODE = LOVE

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