oj.uz

답안 #427907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427907 2021-06-15T04:49:29 Z Kevin_Zhang_TW Long Distance Coach (JOI17_coach) C++17
0 / 100
 5 ms 844 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 cost(int l, int r) {
	if (l > r) return 0;
	ll req = X / T + 10;
	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;
}

struct sgt {
	struct node {
		ll mn, at;
		node () : mn(0), at(0) {}
		node (node a, node b) : at(0) {
			mn = min(a.mn, b.mn);
		}
		void operator += (ll v) {
			mn += v, at += v;
		}
	};
	int n;
	vector<node> val;
	sgt(int n) : n(n) {
		val.resize(n<<1);
	}
	void push(int i) {
		if (i >= n) return;
		ll &at = val[i].at;
		val[i<<1] += at, val[i<<1|1] += at;
		at = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	void add(int l, int r, ll v) {
		int sl = l += n, sr = r += n;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;)
			upd(sl), upd(sr);
	}
	ll qry(int l, int r) {
		ll res = inf;
		l += n, r += n;
		for (int i = MAX_K;i > 0;--i) push(l>>i), push(r>>i);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmin(res, val[l++].mn);
			if (r&1) chmin(res, val[--r].mn);
		}
		return res;
	}
};
// N refill points, and M people
// remember the driver need water too
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;

	deque< int > from, time;
	from.pb(0), time.pb(-1);

	auto trans = [&](int j, int i) {
		return dp[j] + cost(j+1, i-1);
	};

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

		while (from.size() > 1 && time[1] <= i)
			from.pop_front(), time.pop_front();

		DE(i, from[0]);

		dp[i] = sum + trans(from[0], i);

		// tell me when x becomes better than y
		auto better = [&](int x, int y) {
			int l = i+1, r = m, mid;
			while (l < r) {
				mid = l + r >> 1;
				if (trans(x, mid) <= trans(y, mid))
					r = mid;
				else 
					l = mid+1;
			}
			return l;
		};
		while (from.size() > 1) {
			int ti = better(i, from.back());
			if (ti > time.back()) break;
			from.pop_back(), time.pop_back();
		}
		time.pb(better(i, from.back())), from.pb(i);
	}

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

		int p = -1;
		for (int j = 0;j < i;++j) {
			if (chmin(dp[i], sum + trans(j, i)))
				p = j;
		}
		assert(p >= lst);
		lst = p;
		DE(i, p);
	}
}

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;
	for (int i = 0;i < m;++i) {
		chmin(res, dp[i] + cost(i+1, m-1));
	}

	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 function 'll cost(int, int)':
coach.cpp:66:5: warning: unused variable 'req' [-Wunused-variable]
   66 |  ll req = X / T + 10;
      |     ^~~
coach.cpp: In function 'void solve()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:159:3: note: in expansion of macro 'DE'
  159 |   DE(i, from[0]);
      |   ^~
coach.cpp: In lambda function:
coach.cpp:167:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     mid = l + r >> 1;
      |           ~~^~~
coach.cpp: In function 'void solve()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:196:3: note: in expansion of macro 'DE'
  196 |   DE(i, p);
      |   ^~
coach.cpp: In function 'int32_t main()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:204:2: note: in expansion of macro 'DE'
  204 |  DE(X, n, m, W, T);
      |  ^~

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 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 Runtime error 5 ms 844 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 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 Runtime error 5 ms 844 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 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 Runtime error 5 ms 844 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 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 Runtime error 5 ms 844 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -