oj.uz

Submission #36001

# Submission time Handle Problem Language Result Execution time Memory
36001 2017-12-04T07:19:01 Z ngkan146 Pinball (JOI14_pinball) C++
100 / 100
 369 ms 23924 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) 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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20768 KB Output is correct
2 Correct 6 ms 20768 KB Output is correct
3 Correct 3 ms 20768 KB Output is correct
4 Correct 6 ms 20768 KB Output is correct
5 Correct 3 ms 20768 KB Output is correct
6 Correct 6 ms 20768 KB Output is correct
7 Correct 6 ms 20768 KB Output is correct
8 Correct 3 ms 20768 KB Output is correct

Subtask #2
18.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 Correct 3 ms 20768 KB Output is correct
5 Correct 3 ms 20768 KB Output is correct
6 Correct 6 ms 20768 KB Output is correct

Subtask #3
22.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 9 ms 20768 KB Output is correct
5 Correct 6 ms 20768 KB Output is correct
6 Correct 6 ms 20768 KB Output is correct
7 Correct 3 ms 20768 KB Output is correct
8 Correct 9 ms 20768 KB Output is correct
9 Correct 6 ms 20768 KB Output is correct
10 Correct 3 ms 20768 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 21040 KB Output is correct
2 Correct 69 ms 21620 KB Output is correct
3 Correct 206 ms 22388 KB Output is correct
4 Correct 206 ms 23924 KB Output is correct
5 Correct 149 ms 22388 KB Output is correct
6 Correct 266 ms 23924 KB Output is correct
7 Correct 339 ms 23924 KB Output is correct
8 Correct 303 ms 23924 KB Output is correct
9 Correct 56 ms 21236 KB Output is correct
10 Correct 146 ms 22388 KB Output is correct
11 Correct 233 ms 23924 KB Output is correct
12 Correct 369 ms 23924 KB Output is correct
13 Correct 329 ms 23924 KB Output is correct
14 Correct 369 ms 23924 KB Output is correct