Submission #36001

#	Time	Username	Problem	Language	Result	Execution time	Memory
36001		ngkan146	Pinball (JOI14_pinball)	C++98	100 / 100	369 ms	23924 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int l[100005], r[100005], hole[100005], c[100005];
ll seg[2000005];
void seg_upd(int id,int l,int r,int pos,ll val){
	if (r < pos || pos < l)	return;
	if (l == r){
		seg[id] = min(seg[id], val);
		return;
	}
	seg_upd(2*id,  l,  (l+r)/2,pos,val);
	seg_upd(2*id+1,(l+r)/2+1,r,pos,val);
	seg[id] = min(seg[2*id], seg[2*id+1]);
}
ll seg_get(int id,int l,int r,int u,int v){
	if (r < u || v < l)	return (ll) 1e15;
	if (u <= l && r <= v) return seg[id];
	return min(seg_get(2*id,l,(l+r)/2,u,v), seg_get(2*id+1,(l+r)/2+1,r,u,v));
}
ll far_left[100005], far_right[100005];
vector <int> nen;
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d %d",&l[i],&r[i],&hole[i],&c[i]);
		nen.push_back(l[i]);
		nen.push_back(r[i]);
		nen.push_back(hole[i]);
	}
	nen.push_back(1);
	nen.push_back(m);
	sort(nen.begin(), nen.end());
	nen.resize(unique(nen.begin(), nen.end()) - nen.begin());
	for(int i=1;i<=n;i++){
		l[i] = lower_bound(nen.begin(), nen.end(), l[i]) - nen.begin() + 1;
		r[i] = lower_bound(nen.begin(), nen.end(), r[i]) - nen.begin() + 1;
		hole[i] = lower_bound(nen.begin(), nen.end(), hole[i]) - nen.begin() + 1;
	
	}
	m = nen.size();
	
	// do left
	for(int i=1;i<=2000000;i++) seg[i] = (ll) 1e15;
	for(int i=1;i<=n;i++){
		far_left[i] = seg_get(1,1,m,l[i],r[i]);
		if (l[i] == 1) far_left[i] = 0;
		seg_upd(1,1,m,hole[i],far_left[i] + c[i]);
	}
	// do right
	for(int i=1;i<=2000000;i++) seg[i] = (ll) 1e15;
	for(int i=1;i<=n;i++){
		far_right[i] = seg_get(1,1,m,l[i],r[i]);
		if (r[i] == m) far_right[i] = 0;
		seg_upd(1,1,m,hole[i],far_right[i] + c[i]);
	}
	
	
	ll ans = (ll) 1e15;
	for(int i=1;i<=n;i++)
		ans = min(ans, far_left[i] + far_right[i] + c[i]);
	if (ans == (ll) 1e15) printf("-1");
	else printf("%lld",ans);
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
pinball.cpp:27:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&l[i],&r[i],&hole[i],&c[i]);
                                                  ^

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