Submission #853051

#	Time	Username	Problem	Language	Result	Execution time	Memory
853051		epicci23	Pinball (JOI14_pinball)	C++17	100 / 100	478 ms	37192 KiB

pinball

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()


constexpr int INF = 1e18;
 
void update(int pos, int val, vector<int>& tree) {
	int n = sz(tree)/2;
	pos += n;
	while(pos > 0) {
		tree[pos] = min(tree[pos], val);
		pos >>= 1;
	}
}
 
int query(int l, int r, vector<int>& tree) {
	int ans = INF;
	int n = sz(tree)/2;
	l += n,r += n;
	for(; l <= r; l>>=1, r>>=1) {
		if(l%2==1) ans = min(ans, tree[l++]);
		if(r%2==0) ans = min(ans, tree[r--]);
	}
	return ans;
}

void solve(){

	int m,n;
	cin >> m >> n;

	map<int,int> mp;
    mp[1]=mp[n]=1;
    array<int,4> ar[m+1];
	for(int i=1;i<=m;i++){
       int a,b,c,d;
       cin >> a >> b >> c >> d;
       ar[i]={a,b,c,d};
       mp[a]=mp[b]=mp[c]=1;
	}

	int p=0;
	for(auto x:mp) mp[x.first]=p++;

    vector<int> treel(2*p,INF),treer(2*p,INF);
    
    update(0,0,treel);
	update(p-1,0,treer);
    
    vector<int> dpl(m+1,INF);
    vector<int> dpr(m+1,INF);

	for(int i=1;i<=m;i++) {
		int curl=query(mp[ar[i][0]],mp[ar[i][1]],treel);
		dpl[i]=min(dpl[i],curl+ar[i][3]);
		update(mp[ar[i][2]],dpl[i],treel);
	    int curr=query(mp[ar[i][0]],mp[ar[i][1]],treer);
		dpr[i]=min(dpr[i],curr+ar[i][3]);
		update(mp[ar[i][2]],dpr[i],treer);
	}
	int best=INF;
	for(int i=1;i<=m;i++) best=min(best,dpl[i]+dpr[i]-ar[i][3]);
	
	if(best==INF) cout << -1 << endl;
	else cout << best << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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