Submission #754322

#	Time	Username	Problem	Language	Result	Execution time	Memory
754322		parsadox2	Pinball (JOI14_pinball)	C++14	100 / 100	302 ms	27064 KiB

pinball

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long

const int maxn = 4e5 + 10 , inf = 1e18;
int n , l[maxn] , r[maxn] , hole[maxn] , cost[maxn] , m , tree[2][maxn << 2];

void Build(int ty , int node = 1 , int nl = 0 , int nr = n)
{
	if(nr - nl == 1)
	{
		if(ty == 0 && nl == 0)  tree[ty][node] = 0;
		else if(ty == 1 && nr == n)  tree[ty][node] = 0;
		else  tree[ty][node] = inf;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	Build(ty , lc , nl , mid);  Build(ty , rc , mid , nr);
	tree[ty][node] = min(tree[ty][lc] , tree[ty][rc]);
}

void update(int ty , int ind , int val , int node = 1 , int nl = 0 , int nr = n)
{
	if(nr - nl == 1)
	{
		tree[ty][node] = min(tree[ty][node] , val);
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)  update(ty , ind , val , lc , nl , mid);
	else update(ty , ind , val , rc , mid , nr);
	tree[ty][node] = min(tree[ty][lc] , tree[ty][rc]);
}

int Get(int ty , int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
	if(r <= nl || nr <= l)  return inf;
	if(l <= nl && nr <= r)  return tree[ty][node];
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	return min(Get(ty , l , r , lc , nl , mid) , Get(ty , l , r , rc , mid , nr));
}

int32_t main()
{
	fast;
	cin >> m >> n;
	vector <int> vec;
	bool flg = false;
	for(int i = 0 ; i < m ; i++)
	{
		cin >> l[i] >> r[i] >> hole[i] >> cost[i];
		if(l[i] == 1)  flg = true;
		vec.pb(l[i]);  vec.pb(r[i]);  vec.pb(hole[i]);  vec.pb(min(n , r[i] + 1));
	}
	if(n == 1)
	{
		cout << 0 << endl;
		return 0;
	}
	if(!flg)
	{
		cout << -1 << endl;
		return 0;
	}
	sort(vec.begin() , vec.end());
	vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
	n = SZ(vec);
	for(int i = 0 ; i < m ; i++)
	{
		l[i] = lower_bound(vec.begin() , vec.end() , l[i]) - vec.begin();
		r[i] = lower_bound(vec.begin() , vec.end() , r[i]) - vec.begin();
		r[i]++;
		hole[i] = lower_bound(vec.begin() , vec.end() , hole[i]) - vec.begin();
	}
	Build(0);  Build(1);
	int ans = inf;
	for(int i = 0 ; i < m ; i++)
	{
		int r0 = Get(0 , l[i] , r[i]) , r1 = Get(1 , l[i] , r[i]);
		int res = r0 + r1 + cost[i];
		ans = min(ans , res);
		update(0 , hole[i] , r0 + cost[i]);  update(1 , hole[i] , r1 + cost[i]);
	}
	if(ans == inf)   cout << -1 << endl;
	else  cout << ans << endl;
	return 0;
}

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