Submission #78997

#	Time	Username	Problem	Language	Result	Execution time	Memory
78997		Plurm	Pinball (JOI14_pinball)	C++11	11 / 100	2 ms	824 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
const int MXN = 1 << 17;
long long dp1[MXN];
long long dp2[MXN];
long long dp1h[3*MXN];
long long dp2h[3*MXN];
long long segT1[12*MXN];
long long segT2[12*MXN];
int lb[12*MXN];
int rb[12*MXN];
void build(int c,int l,int r){
	lb[c] = l;
	rb[c] = r;
	if(l == r){
		segT1[c] = dp1h[l];
		segT2[c] = dp2h[l];
		return;
	}
	int k = (l+r)/2;
	build(2*c,l,k);
	build(2*c+1,k+1,r);
	segT1[c] = min(segT1[2*c],segT1[2*c+1]);
	segT2[c] = min(segT2[2*c],segT2[2*c+1]);
}
void update1(int c,int idx){
	if(lb[c] == rb[c]){
		segT1[c] = dp1h[idx];
		return;
	}
	int k = (lb[c] + rb[c])/2;
	if(idx <= k){
		update1(2*c,idx);
	}else{
		update1(2*c+1,idx);
	}
	segT1[c] = min(segT1[2*c],segT1[2*c+1]);
}
void update2(int c,int idx){
	if(lb[c] == rb[c]){
		segT2[c] = dp2h[idx];
		return;
	}
	int k = (lb[c] + rb[c])/2;
	if(idx <= k){
		update2(2*c,idx);
	}else{
		update2(2*c+1,idx);
	}
	segT2[c] = min(segT2[2*c],segT2[2*c+1]);
}
long long query1(int c,int l,int r){
	if(lb[c] == l && rb[c] == r) return segT1[c];
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		return min(query1(2*c,l,k),query1(2*c+1,k+1,r));
	}else if(r <= k){
		return query1(2*c,l,r);
	}else{
		return query1(2*c+1,l,r);
	}
}
long long query2(int c,int l,int r){
	if(lb[c] == l && rb[c] == r) return segT2[c];
	int k = (lb[c] + rb[c])/2;
	if(l <= k && k < r){
		return min(query2(2*c,l,k),query2(2*c+1,k+1,r));
	}else if(r <= k){
		return query2(2*c,l,r);
	}else{
		return query2(2*c+1,l,r);
	}
}
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	vector<tuple<int,int,int,int> > data;
	vector<int> cprs;
	for(int i = 0; i < m; i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		data.emplace_back(a,b,c,d);
		cprs.push_back(a);
		cprs.push_back(b);
		cprs.push_back(c);
		dp1[i] = dp2[i] = 1e18;
	}
	sort(cprs.begin(),cprs.end());
	cprs.resize(unique(cprs.begin(),cprs.end()) - cprs.begin());
	for(int i = 0; i < cprs.size(); i++){
		dp1h[i] = dp2h[i] = 1e18;
	}
	build(1,0,cprs.size()-1);
	for(int i = 0; i < m; i++){
		if(get<0>(data[i]) == 1){
			dp1[i] = get<3>(data[i]);
			dp1h[lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin()] = dp1[i];
			update1(1,lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin());
		}
		if(get<1>(data[i]) == n){
			dp2[i] = get<3>(data[i]);
			dp2h[lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin()] = dp2[i];
			update2(1,lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin());
		}

		dp1[i] = min(dp1[i],(long long)get<3>(data[i]) + query1(1,
			lower_bound(cprs.begin(),cprs.end(),
				get<0>(data[i])) - cprs.begin(),
			lower_bound(cprs.begin(),cprs.end(),
				get<1>(data[i])) - cprs.begin())
		);
		dp1h[lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin()] = min(dp1h[i],dp1[i]);
		update1(1,lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin());

		dp2[i] = min(dp2[i],(long long)get<3>(data[i]) + query2(1,
			lower_bound(cprs.begin(),cprs.end(),
				get<0>(data[i])) - cprs.begin(),
			lower_bound(cprs.begin(),cprs.end(),
				get<1>(data[i])) - cprs.begin())
		);
		dp2h[lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin()] = min(dp2h[i],dp2[i]);
		update2(1,lower_bound(cprs.begin(),cprs.end(),get<2>(data[i])) - cprs.begin());
		
	}
	long long mn = 1e18;
	for(int i = 0; i < m; i++){
		mn = min(mn,dp1[i] + dp2[i] - get<3>(data[i]));
	}
	if(mn == 1e18){
		printf("-1\n");
	}else{
		printf("%lld\n",mn);
	}
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cprs.size(); i++){
                 ~~^~~~~~~~~~~~~
pinball.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&m,&n);
  ~~~~~^~~~~~~~~~~~~~
pinball.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&a,&b,&c,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49