oj.uz

답안 #109183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109183 2019-05-05T11:15:29 Z maruii Pinball (JOI14_pinball) C++14
0 / 100
 16 ms 16768 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SIZE = 1<<19;
struct ST{
	ll data[2*SIZE];
	void init(){fill(data, data+2*SIZE, 1e18);}
	void update(int x, ll v){
		for(x+=SIZE; x; x>>=1) data[x] = min(data[x], v);
	}
	ll query(int s, int e){
		ll ret = 1e18;
		for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
			if( s&1) ret = min(ret, data[s++]);
			if(~e&1) ret = min(ret, data[e--]);
		}
		return ret;
	}
} seg1, seg2;

int A[100000], B[100000], C[100000], D[100000];
vector<int> xx;
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int M, N; cin>>M>>N;
	for(int i=0; i<M; ++i){
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		xx.push_back(A[i]), xx.push_back(B[i]), xx.push_back(C[i]);
	}
	xx.push_back(1), xx.push_back(N);
	sort(xx.begin(), xx.end()), xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for(int i=0; i<M; ++i){
		A[i] = lower_bound(xx.begin(), xx.end(), A[i]) - xx.begin();
		B[i] = lower_bound(xx.begin(), xx.end(), B[i]) - xx.begin();
		C[i] = lower_bound(xx.begin(), xx.end(), C[i]) - xx.begin();
	}
	seg1.init(), seg2.init(), seg1.update(0, 0), seg2.update(xx.size()-1, 0);
	long long ans = 1e18;
	for(int i=0; i<M; ++i){
		ll s = seg1.query(A[i], B[i]), t = seg2.query(A[i], B[i]);
		if(seg1.query(C[i], C[i]) > D[i] + s) seg1.update(C[i], D[i] + t);
		if(seg2.query(C[i], C[i]) > D[i] + t) seg2.update(C[i], D[i] + t);
		ans = min(ans, D[i] + s + t);
	}
	if(ans == 1e18) ans = -1;
	cout<<ans;
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 16 ms 16768 KB Output is correct
4 Correct 16 ms 16768 KB Output is correct
5 Correct 15 ms 16768 KB Output is correct
6 Incorrect 15 ms 16768 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 16 ms 16768 KB Output is correct
4 Correct 16 ms 16768 KB Output is correct
5 Correct 15 ms 16768 KB Output is correct
6 Incorrect 15 ms 16768 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 16 ms 16768 KB Output is correct
4 Correct 16 ms 16768 KB Output is correct
5 Correct 15 ms 16768 KB Output is correct
6 Incorrect 15 ms 16768 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Correct 16 ms 16768 KB Output is correct
4 Correct 16 ms 16768 KB Output is correct
5 Correct 15 ms 16768 KB Output is correct
6 Incorrect 15 ms 16768 KB Output isn't correct
7 Halted 0 ms 0 KB -