Submission #109183

#	Time	Username	Problem	Language	Result	Execution time	Memory
109183		maruii	Pinball (JOI14_pinball)	C++14	0 / 100	16 ms	16768 KiB

pinball

#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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49