Submission #56571

#	Time	Username	Problem	Language	Result	Execution time	Memory
56571		Mamnoon_Siam	Pinball (JOI14_pinball)	C++17	100 / 100	468 ms	14140 KiB

pinball

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define int long long
typedef long long ll;

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

const ll inf = 1e18;

struct MinSegTree {
	vector<ll> t;
	MinSegTree() {}
	MinSegTree(int N) {t.assign(N << 1, inf);}
	void update(int p, ll val) {
		p += (t.size() >> 1);
		t[p] = min(t[p], val);
		for(; p > 1; p >>= 1) t[p >> 1] = min(t[p], t[p ^ 1]);
	}
	ll query(int l, int r) {
		r++;
		ll ret = inf;
		for(l += (t.size() >> 1), r += (t.size() >> 1); l < r; l >>= 1, r >>= 1) {
			if(l & 1) ret = min(ret, t[l++]);
			if(r & 1) ret = min(ret, t[--r]);
		} return ret;
	}
};

int m, n;
vector<int> A, B, C;
vector<ll> D;
const int maxn = 100005;
ll pre[maxn], suf[maxn];

void compress() {
	vector<ll> temp;
	for(int i = 0; i < m; i++) {
		temp.push_back(A[i]);
		temp.push_back(B[i]);
		temp.push_back(C[i]);
	} temp.push_back(n);
	temp.push_back(1);
	sort(all(temp));
	KeepUnique(temp);
	for(int i = 0; i < m; i++) {
		A[i] = lower_bound(all(temp), A[i]) - temp.begin();
		B[i] = lower_bound(all(temp), B[i]) - temp.begin();
		C[i] = lower_bound(all(temp), C[i]) - temp.begin();
	} n = lower_bound(all(temp), n) - temp.begin();
}

int32_t main () {
	// freopen("in", "r", stdin);
	cin >> m >> n;
	A.resize(m), B.resize(m), C.resize(m), D.resize(m);
	for(int i = 0; i < m; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}
	compress();
	MinSegTree ds;
	ds = MinSegTree(n + 10);
	for(int i = 0; i < m; i++) {
		pre[i] = A[i] == 0 ? D[i] : inf;
		pre[i] = min(pre[i], D[i] + ds.query(A[i], B[i]));
		ds.update(C[i], pre[i]);
	}
	ds = MinSegTree(n + 10);
	for(int i = 0; i < m; i++) {
		suf[i] = B[i] == n ? D[i] : inf;
		suf[i] = min(suf[i], D[i] + ds.query(A[i], B[i]));
		ds.update(C[i], suf[i]);
	}
	ll ret = inf;
	for(int i = 0; i < m; i++) {
		ret = min(ret, pre[i] + suf[i] - D[i]);
	}
	if(ret == inf) cout << "-1" << endl;
	else cout << ret << endl;
}

Compilation message (stderr)

pinball.cpp: In function 'long long int myrand(long long int, long long int)':
pinball.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
pinball.cpp:18:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~

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