Submission #94808

#	Time	Username	Problem	Language	Result	Execution time	Memory
94808		Retro3014	Pinball (JOI14_pinball)	C++17	100 / 100	182 ms	12160 KiB

pinball

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

#define INF 1000000000000000000LL
#define MAX_N 1000000000
#define MAX_M 100000
typedef long long ll;
using namespace std;

int M, N;
struct S1{
	int a, b, c, d;
	int idx;
};
struct S2{
	int idx, x;
	bool operator <(const S2 &a){
		return x<a.x;
	}
};
vector<S1> v1;
vector<S2> v2;
vector<int> v3;
int two = 1;
ll seg1[MAX_M*4+1], seg2[MAX_M*4+1];
ll ans = INF;

void update1(int x, ll y){
	x+=two;
	while(x>0){
		seg1[x] = min(seg1[x], y);
		x/=2;
	}
}

void update2(int x, ll y){
	x+=two;
	while(x>0){
		seg2[x] = min(seg2[x], y);
		x/=2;
	}
}

ll cmin1(int x, int y){
	x+=two; y+=two;
	ll ret = INF;
	while(x<=y){
		if(x==y)	return min(ret, seg1[x]);
		if(x%2)	ret = min(ret, seg1[x++]);
		if(!(y%2))	ret = min(ret, seg1[y--]);
		x/=2; y/=2;
	}return ret;
}

ll cmin2(int x, int y){
	x+=two; y+=two;
	ll ret = INF;
	while(x<=y){
		if(x==y)	return min(ret, seg2[x]);
		if(x%2)	ret = min(ret, seg2[x++]);
		if(!(y%2))	ret = min(ret, seg2[y--]);
		x/=2; y/=2;
	}return ret;
}

void init(int x){
	while(two<=x)	two*=2;
	for(int i=1; i<two*2; i++){
		seg1[i] = seg2[i] = INF;
	}
	update1(0, 0); update2(x-1, 0);
}


int main(){
	scanf("%d %d", &M, &N);
	init(M+2);
	for(int i=0; i<M; i++){
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		v1.push_back({a, b, c, d, 0});
		v2.push_back({i, c});
	}
	sort(v2.begin(), v2.end());
	for(int i=0; i<v2.size(); i++){
		v1[v2[i].idx].idx = i+1;
		v3.push_back(v2[i].x);
	}
	v3.push_back(1);
	v3.push_back(N);
	sort(v3.begin(), v3.end());
	for(int i=0; i<v1.size(); i++){
		S1 now = v1[i];
		int s, e;
		s = lower_bound(v3.begin(), v3.end(), now.a) - v3.begin();
		e = upper_bound(v3.begin(), v3.end(), now.b) - v3.begin() - 1;
		ans = min(ans, cmin1(s, e)+cmin2(s, e)+now.d);
		if(cmin1(s, e)!=INF)	update1(now.idx, cmin1(s, e)+(ll)now.d);
		if(cmin2(s, e)!=INF)	update2(now.idx, cmin2(s, e)+(ll)now.d);
	}
	if(ans==INF){
		printf("-1");
	}else{
		printf("%lld", ans);
	}
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
pinball.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v1.size(); i++){
               ~^~~~~~~~~~
pinball.cpp:78: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:82: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: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49