Submission #25266

#	Time	Username	Problem	Language	Result	Execution time	Memory
25266		kajebiii	Pinball (JOI14_pinball)	C++14	100 / 100	286 ms	22108 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

int N, M;
struct IDX {
	int P; vector<ll> val;
	IDX(int n) {
		for(P=1; P<n; P<<=1);
		val = vector<ll>(2*P, LINF);
	}
	void update(int v, ll k) {
		if(val[v+=P] <= k) return;
		val[v] = k;
		while(v/=2) val[v] = min(val[v*2], val[v*2+1]);
	}
	ll getMin(int a, int b) {
		a+=P, b+=P;
		ll res = LINF;
		while(a<=b) {
			if(a%2==1) res = min(res, val[a++]);
			if(b%2==0) res = min(res, val[b--]);
			a>>=1;b>>=1;
		}
		return res;
	}
};

const int MAX_N = 1e5 + 100;

int Nr[MAX_N][4];
vector<int> Co;
int main() {
	cin >> N >> M;
	REP(i, N) REP(j, 4) {
		scanf("%d", &Nr[i][j]);
		if(j < 3) Co.push_back(Nr[i][j]);
	}
	Co.push_back(1), Co.push_back(M);
	sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());
	REP(i, N) REP(j, 3) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin();
	IDX idx[2] = {IDX(SZ(Co)), IDX(SZ(Co))};

	idx[0].update(0, 0ll); idx[1].update(SZ(Co)-1, 0ll);

	ll ans = LINF;
	REP(i, N) {
		int a = Nr[i][0], b = Nr[i][1], c = Nr[i][2], d = Nr[i][3];
		ans = min(ans, idx[0].getMin(a, b) + idx[1].getMin(a, b) + d);
		idx[0].update(c, idx[0].getMin(a, b) + d);
		idx[1].update(c, idx[1].getMin(a, b) + d);
	}
	if(ans == LINF) ans = -1;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:47:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Nr[i][j]);
                         ^

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