oj.uz

Submission #428030

# Submission time Handle Problem Language Result Execution time Memory
428030 2021-06-15T07:25:54 Z Kevin_Zhang_TW Long Distance Coach (JOI17_coach) C++17
16 / 100
 1 ms 588 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing

const int MAX_N = 200010, MAX_K = 18;
const ll inf = 2e18;

ll X, n, m, W, T;
ll s[MAX_N];

ll dp[MAX_N], sp[MAX_N], pfc[MAX_N];

pair<ll,ll> man[MAX_N];

int nxt[MAX_K][MAX_N];
ll jsum[MAX_K][MAX_N];

void init_cost() {
	{
		ll sum = 0;
		for (int i = 0;i < m;++i) {
			pfc[i] = sum += man[i].second;
		}
	}
	debug(sp, sp+m);
	vector<int> stk {0};
	sp[0] = 0;
	for (int i = 0;i < m;++i) {
		while (stk.size()) {
			int id = stk.back();
			if (sp[i] >= sp[id]) break;
			stk.pop_back();
		}
		nxt[0][i] = stk.back();
		jsum[0][i] = W * (i-stk.back()) * sp[i];
		stk.pb(i);
	}
	for (int d = 1;d < MAX_K;++d) {
		for (int i = 0;i < m;++i) {
			nxt[d][i] = nxt[d-1][ nxt[d-1][i] ];
			jsum[d][i] = jsum[d-1][i] + jsum[d-1][ nxt[d-1][i] ];
		}
	}
}
ll pay(int l, int r) {
	if (l > r) return 0;
	ll ret = pfc[r] - (l?pfc[l-1]:0);
	for (int d = MAX_K-1;d >= 0;--d) {
		if (nxt[d][r] < l) continue;
		ret += jsum[d][r];
		r = nxt[d][r];
	}
	assert(r >= l);
	assert(nxt[0][r] < l);
	ret += sp[r] * (r-l+1) * W;

	return ret;
}
ll cost(int l, int r) {
	return dp[l] + pay(l+1, r-1);
}

// N refill points, and M people
// remember the driver need water too

ll F(pair<ll,ll> a, ll x) { return a.first * x + a.second; }

// floor ( y / x )
ll fdiv(ll a, ll b) {
	assert( b > 0 );
	return a / b - (a < 0 && a % b);
}

ll inter(pair<ll,ll> a, pair<ll,ll> b) {
	if (a < b) swap(a, b);
	auto [m1, v1] = a;
	auto [m2, v2] = b;
	assert(m1 > m2);
	return fdiv(v2 - v1, m1 - m2);
}

// slope in deque is decreasing
struct minconv {
	deque< pair<ll,ll> > dq;
	// put a line, and the line has the maximum slope
	void pb(pair<ll,ll> line) {
		if (false)
		while (dq.size() > 1) {
			auto a = dq[0], b = dq[1];
			if (inter(line, a) < inter(a, b)) break;
			dq.pop_front();
		}
		dq.push_front(line);
	}
	// put a line, and the line has the minimum slope
	void pf(pair<ll,ll> line) {
		if (false)
		while (dq.size() > 1) {
			auto a = end(dq)[-2], b = end(dq)[-1];
			if (inter(a, b) < inter(b, line)) break;
			dq.pop_back();
		}
		dq.push_back(line);
	}
	pair<ll,ll> pop_back() { auto ret = dq.back(); dq.pop_back(); return ret; }
	pair<ll,ll> pop_front() { auto ret = dq.front(); dq.pop_front(); return ret; }
	int qq(int i) {
		ll v = inf, ret = 0;
		for (int j = 0;j < dq.size();++j)
			if (chmin(v, cost(dq[j].first, i)))
				ret = dq[j].first;
		return ret;
	}
	int qrypoint(ll x) {
		assert(dq.size());

		ll v = inf, ret = 0;
		for (int i = 0;i < dq.size();++i)
			if (chmin(v, F(dq[i], x)))
				ret = dq[i].first;
		return ret;

		int l = 0, r = (int) dq.size() - 1, mid;
		while (l < r) {
			mid = l + r >> 1;
			if (F(dq[mid], x) <= F(dq[mid+1], x))
				r = mid;
			else
				l = mid+1;
		}
		return dq[l].first;
	}
};
// put to b
void merge_conv(minconv &a, minconv &b) {
	if (a.dq.size() < b.dq.size()) 
		while (a.dq.size()) b.pf(a.pop_front());
	else {
		while (b.dq.size()) a.pb(b.pop_back());
		swap(a, b);
	}
}

pair<ll,ll> get_line(int ind) { 
	return make_pair(ind, dp[ind] - pfc[ind]);
}
vector<int> stk;
vector<minconv> conv;
vector<int> bst;
void solve() {
	fill(dp, dp + m, inf);
	fill(sp, sp + m, X / T + 10);
	sort(s, s + n);
	sort(man, man + m);

	for (int i = 0;i < n;++i) {
		ll spt = s[i] / T;
		int p = lower_bound(man, man + m, make_pair(s[i] % T, 0ll)) - man;
		chmin(sp[p-1], spt);
	}

	init_cost();

	dp[0] = (X / T + (X % T > man[0].first)) * W;

	stk.pb(0);
	conv.pb(); conv[0].pb(get_line(0));
	bst.pb(0);

	for (int i = 1;i < m;++i) {
		auto [d, c] = man[i];
		ll sum = (X / T + (X % T > d)) * W ;

		//int id = conv.back().qrypoint(-sp[i-1]);
		int id = conv.back().qq(i);

		if (bst.size() > 1) 
			chmin(dp[i], sum + cost(end(bst)[-2], i));

		chmin(dp[i], sum + cost(id, i));

		minconv cur;
		cur.pb(get_line(i));

		while (stk.size()) {
			int r = stk.back();
			if (sp[r] < sp[i]) break;
			merge_conv(conv.back(), cur);
			assert(conv.back().dq.empty());
			bst.pop_back();
			conv.pop_back();
			stk.pop_back();
		}

		bst.pb( bst.empty() || cost(bst.back(), i+1) > cost(id, i+1) ? id : bst.back() );
		stk.pb(i);
		conv.pb();
		swap(cur, conv.back());

		//for (int j = 0;j < i;++j) chmin(dp[i], sum + cost(j, i));
	}
//
//	for (int i = 1;i < m;++i) {
//		auto [d, c] = man[i];
//		ll sum = (X / T + (X % T > d)) * W ;// + (i-1) * sp[i-1];
//
//		for (int j = 0;j < i;++j) {
//			chmin(dp[i], sum + cost(j, i));
//		}
//	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> X >> n >> m >> W >> T;

	DE(X, n, m, W, T);
	for (int i = 0;i < n;++i)
		cin >> s[i];
	s[n++] = X;

	for (int i = 0;i < m;++i) {
		auto &[d, c] = man[i];
		cin >> d >> c;
	}
	man[m++] = make_pair(0, inf);
	
	solve();

	ll res = inf;

	ll req = (X / T + 10), sum = 0;
	for (int i = m-1;i >= 0;--i) {
		chmin(res, dp[i] + sum);
		chmin(req, sp[i]);
		sum += req * W + man[i].second;
	}

	cout << res << '\n';
}

Compilation message

coach.cpp: In function 'void init_cost()':
coach.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
coach.cpp:44:2: note: in expansion of macro 'debug'
   44 |  debug(sp, sp+m);
      |  ^~~~~
coach.cpp: In member function 'int minconv::qq(int)':
coach.cpp:128:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for (int j = 0;j < dq.size();++j)
      |                  ~~^~~~~~~~~~~
coach.cpp: In member function 'int minconv::qrypoint(ll)':
coach.cpp:137:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for (int i = 0;i < dq.size();++i)
      |                  ~~^~~~~~~~~~~
coach.cpp:144:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |    mid = l + r >> 1;
      |          ~~^~~
coach.cpp: In function 'int32_t main()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:236:2: note: in expansion of macro 'DE'
  236 |  DE(X, n, m, W, T);
      |  ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Incorrect 1 ms 588 KB Output isn't correct
24 Halted 0 ms 0 KB -