Submission #340178

#	Time	Username	Problem	Language	Result	Execution time	Memory
340178		Bill_00	Pinball (JOI14_pinball)	C++14	51 / 100	1089 ms	72392 KiB

pinball

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define M 100005
#define MAX 1e18
typedef long long ll; 
using namespace std;
ll m,n,L,R,ans=MAX;
ll a[M],b[M];
ll c[M],d[M];

unordered_map<ll,bool>vis[2];
unordered_map<ll,ll>mn[2];

void update(bool type,ll up,ll id=1,ll l=1,ll r=n){
	if(r<L || R<l) return;
	if(L<=l && r<=R){
		if(vis[type][id]){
			mn[type][id]=min(mn[type][id],up);
		}
		else mn[type][id]=up;
		vis[type][id]=1;
		return;
	}
	ll m=l+r>>1;
	update(type,up,id*2,l,m);
	update(type,up,id*2+1,m+1,r);
	if(!vis[type][id*2+1]){
		mn[type][id]=mn[type][id*2];
		vis[type][id]=1;
		return;
	}
	if(!vis[type][id*2]){
		mn[type][id]=mn[type][id*2+1];
		vis[type][id]=1;
		return;
	}
	mn[type][id]=min(mn[type][id*2],mn[type][id*2+1]);
	vis[type][id]=1;
}

ll query(bool type,ll id=1,ll l=1,ll r=n){
	if(r<L | R<l) return MAX;
	if(L<=l && r<=R){
		if(vis[type][id]) return mn[type][id];
		else return MAX;
	}
	ll m=l+r>>1;
	return min(query(type,id*2,l,m),query(type,id*2+1,m+1,r));
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n;
	for(int i=1;i<=m;++i){
		cin >> a[i] >> b[i];
		cin >> c[i] >> d[i];
	}
	L=R=1;
	update(0,0);
	L=R=n;
	update(1,0);
	for(int i=1;i<=m;++i){
		L=a[i],R=b[i];
		ll cost1=query(0);
		ll cost2=query(1);
		if(cost1!=MAX && cost2!=MAX){
			ans=min(ans,cost1+cost2+d[i]);
		}
		L=R=c[i];
		if(cost1!=MAX){
			update(0,cost1+d[i]);
		}
		if(cost2!=MAX){
			update(1,cost2+d[i]);
		}
	}
	if(ans==MAX) cout << -1;
	else cout << ans;
}

Compilation message (stderr)

pinball.cpp: In function 'void update(bool, ll, ll, ll, ll)':
pinball.cpp:27:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  ll m=l+r>>1;
      |       ~^~
pinball.cpp: In function 'll query(bool, ll, ll, ll)':
pinball.cpp:45:6: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   45 |  if(r<L | R<l) return MAX;
      |     ~^~
pinball.cpp:50:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  ll m=l+r>>1;
      |       ~^~

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