Submission #536147

#	Time	Username	Problem	Language	Result	Execution time	Memory
536147		michao	Pinball (JOI14_pinball)	C++14	100 / 100	884 ms	50092 KiB

pinball

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<19;
const int inf=(int)1e18+9;
int a[MAX];
int b[MAX];
int c[MAX];
int d[MAX];
int s1[MAX],s2[MAX];
int t[MAX*2];
map<int,int>compress;
set<int>pom;

int id(int x){
	return compress[x];
}
int dp1[MAX],dp2[MAX];
void wypelnij(){
	fill(t,t+MAX*2,inf);
}

void update(int u,int c){
  u+=MAX;
  t[u]=min(t[u],c);
	for (;u>1;u>>=1){
		t[u>>1]=min(t[u],t[u^1]);
	}
}

int query(int u,int v){
	int mini=inf;
	for (u+=MAX,v+=MAX+1;u<v;u>>=1,v>>=1){
		if (u&1)mini=min(mini,t[u++]);
		if (v&1)mini=min(mini,t[--v]);
	}	
	return mini;
}

int ans=inf;

int32_t main(){
  BOOST;
  int n,m;
  cin>>m>>n;
  pom.ins(1);
  pom.ins(n);
  for (int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		pom.ins(a[i]);
		pom.ins(b[i]);
		pom.ins(c[i]);
  }
  int cnt=1;
  for (auto it:pom)compress[it]=cnt++;
  wypelnij();
	update(id(1),0);
  for (int i=1;i<=m;i++){
		s1[i]=min(inf,query(id(a[i]),id(b[i]))+d[i]);
		update(id(c[i]),s1[i]);
  }
  wypelnij();
  update(id(n),0);
  for (int i=1;i<=m;i++){
		s2[i]=min(inf,query(id(a[i]),id(b[i]))+d[i]);
		update(id(c[i]),s2[i]);
		if (s1[i]==inf || s2[i]==inf)continue;
		ans=min(ans,s1[i]+s2[i]-d[i]);
  }
  
  if (ans==inf)ans=-1;
  cout<<ans;
  return 0; 
}

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