oj.uz

답안 #36001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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