Submission #934946

#	Time	Username	Problem	Language	Result	Execution time	Memory
934946		vjudge1	Pinball (JOI14_pinball)	C++17	0 / 100	8 ms	29276 KiB

pinball

#include <bits/stdc++.h>

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 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;
}

//values
const ll maxn = 1e5 + 1e3;
const ll INF = 1e18;

struct node
{
	ll a;
	ll b;
	ll c;
	ll d;
}a[maxn];

ll m, nn;
map<ll, ll> Find;
set<ll> nums;
ll n = 0;

ll seg[maxn * 12], segL[maxn * 12], segR[maxn * 12];
ll ns = 1;

//functions
void update(ll u ,ll l, ll r, ll pos, ll val)
{
	if(l == r)
	{
		seg[u] = Min(seg[u], val);
		return;
	}
	
	ll mid = (l + r) >> 1;
	if(mid <= pos)
		update(u << 1, l, mid, pos, val);
	else 
		update(u << 1 | 1, mid+1, r, pos, val);
		
	seg[u] = Min(seg[u << 1], seg[u << 1 | 1]);
}

void updateL(ll u ,ll l, ll r, ll pos, ll val)
{
	if(l == r)
	{
		segL[u] = Min(segL[u], val);
		return;
	}
	
	ll mid = (l + r) >> 1;
	if(mid <= pos)
		updateL(u << 1, l, mid, pos, val);
	else 
		updateL(u << 1 | 1, mid+1, r, pos, val);
		
	segL[u] = Min(segL[u << 1], segL[u << 1 | 1]);
}

void updateR(ll u ,ll l, ll r, ll pos, ll val)
{
	if(l == r)
	{
		segR[u] = Min(segR[u], val);
		return;
	}
	
	ll mid = (l + r) >> 1;
	if(mid <= pos)
		updateR(u << 1, l, mid, pos, val);
	else 
		updateR(u << 1 | 1, mid+1, r, pos, val);
		
	segR[u] = Min(segR[u << 1], segR[u << 1 | 1]);
}

ll get(ll u, ll l, ll r, ll tl, ll tr)
{
	if(l > tr or r < tl)return INF;
	if(l >= tl and r <= tr)return seg[u];
	
	ll mid = (l + r) >> 1;
	return Min(get(u << 1, l, mid, tl, tr), get(u << 1 | 1, mid+1, r, tl, tr));
}

ll getL(ll u, ll l, ll r, ll tl, ll tr)
{
	if(l > tr or r < tl)return INF;
	if(l >= tl and r <= tr)return segL[u];
	
	ll mid = (l + r) >> 1;
	return Min(getL(u << 1, l, mid, tl, tr), getL(u << 1 | 1, mid+1, r, tl, tr));
}

ll getR(ll u, ll l, ll r, ll tl, ll tr)
{
	if(l > tr or r < tl)return INF;
	if(l >= tl and r <= tr)return segR[u];
	
	ll mid = (l + r) >> 1;
	return Min(getR(u << 1, l, mid, tl, tr), getR(u << 1 | 1, mid+1, r, tl, tr));
}

void solve()
{
	cin >> m >> nn;
	
	For(i, m)
	{
		cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
		nums.insert(a[i].a);
		nums.insert(a[i].b);
		nums.insert(a[i].c);
	}
	
	nums.insert(1);
	nums.insert(m);
	
	for(auto x : nums)Find[x] = ++n;
			
	For(i,maxn * 12)
		seg[i] = segL[i] = segR[i] = INF;
		
	while(ns < n)ns <<= 1;
	
	updateL(1, 1, ns, 1, 0);
	updateR(1, 1, ns, ns, 0);
	
	For(i,m)
	{
		ll L = getL(1, 1, ns, Find[a[i].a], Find[a[i].b]);
		ll R = getR(1, 1, ns, Find[a[i].a], Find[a[i].b]);
		ll B = get(1, 1, ns, Find[a[i].a], Find[a[i].b]);
		
		ll pos, val;
		//L
		if(L != INF)
		{
			pos = Find[a[i].c];
			val = a[i].d + L;
			updateL(1, 1, ns, pos, val);
		}
		
		//R
		if(R != INF)
		{
			pos = Find[a[i].c];
			val = a[i].d + L;
			updateL(1, 1, ns, pos, val);
		}
		
		//B
		if(R != INF and L != INF)
		{
			pos = Find[a[i].c];
			val = Min(a[i].d + L + R, a[i].d + B);
			update(1, 1, ns, pos, val);
		}
		
	}
	
	ll ans = INF;
	for(int i = 1;i <= ns; i++)ans = Min(ans, get(1, 1, ns, i, i));
	
	if(ans == INF)cout << -1 << endl;
	else cout << ans << endl;
}

int main()
{
	FAST;
	solve();
}

Compilation message (stderr)

pinball.cpp: In function 'void solve()':
pinball.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
pinball.cpp:140:2: note: in expansion of macro 'For'
  140 |  For(i, m)
      |  ^~~
pinball.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
pinball.cpp:153:2: note: in expansion of macro 'For'
  153 |  For(i,maxn * 12)
      |  ^~~
pinball.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
pinball.cpp:161:2: note: in expansion of macro 'For'
  161 |  For(i,m)
      |  ^~~

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