oj.uz

Submission #36000

# Submission time Handle Problem Language Result Execution time Memory
36000 2017-12-04T06:51:29 Z ngkan146 Pinball (JOI14_pinball) C++
0 / 100
 23 ms 21040 KB 
#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) 1e18;
	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;
		//cout << l[i] << ' ' << r[i] << ' ' << hole[i] << endl;
	}
	m = nen.size();
	
	// do left
	for(int i=1;i<=2000000;i++) seg[i] = (ll) 1e18;
	for(int i=1;i<=n;i++){
		far_left[i] = seg_get(1,1,n,l[i],r[i]);
		if (l[i] == 1) far_left[i] = 0;
		seg_upd(1,1,n,hole[i],far_left[i] + c[i]);
	}
	// do right
	for(int i=1;i<=2000000;i++) seg[i] = (ll) 1e18;
	for(int i=1;i<=n;i++){
		far_right[i] = seg_get(1,1,n,l[i],r[i]);
		if (r[i] == m) far_right[i] = 0;
		seg_upd(1,1,n,hole[i],far_right[i] + c[i]);
	}
	ll ans = (ll) 1e18;
	for(int i=1;i<=n;i++)
		ans = min(ans, far_left[i] + far_right[i] + c[i]);
	if (ans == (ll) 1e18) printf("-1");
	else printf("%lld",ans);
}

Compilation message

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20768 KB Output is correct
2 Incorrect 9 ms 20768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20768 KB Output is correct
2 Correct 0 ms 20768 KB Output is correct
3 Correct 6 ms 20768 KB Output is correct
4 Incorrect 6 ms 20768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20768 KB Output is correct
2 Correct 3 ms 20768 KB Output is correct
3 Correct 6 ms 20768 KB Output is correct
4 Correct 3 ms 20768 KB Output is correct
5 Correct 3 ms 20768 KB Output is correct
6 Correct 9 ms 20768 KB Output is correct
7 Incorrect 13 ms 20768 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 21040 KB Output isn't correct
2 Halted 0 ms 0 KB -