Submission #1061627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061627		rainboy	Train (APIO24_train)	C++17	100 / 100	530 ms	56436 KiB

train

#include "train.h"
#include <cstdlib>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 100000, M = 100000, L = 100000, M_ = (M + L) * 2;
const int LG = 19, M1 = M_ * (LG + 1) + 1;	/* LG = ceil(log2((M + L) * 2)) */
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int cc[N];
int ii[M], jj[M];
int xx[M_], hh[M_];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
		while (j < k) {
			int c = xx[hh[j]] != xx[h] ? (xx[hh[j]] < xx[h] ? -1 : 1) : (h & 1) - (hh[j] & 1);
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int ll[M1], rr[M1], kk[M1];

int update(int t, int l, int r, int i) {
	static int _ = 1;
	int t_ = _++;
	ll[t_] = ll[t], rr[t_] = rr[t], kk[t_] = kk[t] + 1;
	if (r - l > 1) {
		int m = (l + r) / 2;
		if (i < m)
			ll[t_] = update(ll[t_], l, m, i);
		else
			rr[t_] = update(rr[t_], m, r, i);
	}
	return t_;
}

int query(int t, int l, int r, int ql) {
	if (r <= ql || t == 0)
		return 0;
	if (l >= ql)
		return kk[t];
	int m = (l + r) / 2;
	return query(ll[t], l, m, ql) + query(rr[t], m, r, ql);
}

int tt[M_], m_;
long long dp[M];

long long eval(int h, int r) {
	return dp[h] + (long long) query(tt[r], 0, m_, xx[h << 1 | 1]) * cc[jj[h]];
}

int find_r(int h1, int h2) {
	int lower = xx[h2 << 1 | 1] - 1, upper = m_;
	while (upper - lower > 1) {
		int r = (lower + upper) / 2;
		if (eval(h1, r) >= eval(h2, r))
			upper = r;
		else
			lower = r;
	}
	return upper;
}

int *eh[N], *er[N], eo[N], eo_[N], oo[N];

void add(int i, int h) {
	while (eo[i] >= 2 && eval(eh[i][eo[i] - 1], er[i][eo[i] - 2]) >= eval(h, er[i][eo[i] - 2]))
		eo[i]--;
	if (eo[i])
		oo[i] = min(oo[i], eo[i] - 1);
	int o = eo[i]++;
	if (o == eo_[i]) {
		eo_[i] *= 2;
		eh[i] = (int *) realloc(eh[i], eo_[i] * sizeof *eh[i]);
		er[i] = (int *) realloc(er[i], eo_[i] * sizeof *er[i]);
	}
	eh[i][o] = h;
	if (o > 0) {
		er[i][o - 1] = find_r(eh[i][o - 1], h);
		if (er[i][o - 1] == m_)
			eo[i]--;
	}
}

long long query_(int i, int r) {
	long long x;
	if (eo[i] == 0)
		x = INF;
	else {
		while (oo[i] + 1 < eo[i] && er[i][oo[i]] <= r)
			oo[i]++;
		x = eval(eh[i][oo[i]], r);
	}
	if (i == 0)
		x = min(x, (long long) query(tt[r], 0, m_, 0) * cc[0]);
	return x;
}

long long solve(int n, int m, int l, vi cc_, vi ii_, vi jj_, vi aa, vi bb, vi ww, vi ll, vi rr) {
	for (int i = 0; i < n; i++)
		cc[i] = cc_[i];
	for (int h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h];
	for (int h = 0; h < m; h++)
		xx[h << 1 | 0] = aa[h], xx[h << 1 | 1] = bb[h];
	for (int h = 0; h < l; h++)
		xx[m + h << 1 | 0] = ll[h] - 1, xx[m + h << 1 | 1] = rr[h] + 1;
	m_ = (m + l) * 2;
	for (int h = 0; h < m_; h++)
		hh[h] = h;
	sort(hh, 0, m_);
	for (int h = 0; h < m_; h++)
		xx[hh[h]] = h;
	for (int h = 0, t = 0; h < m_; h++) {
		int h_ = hh[h] >> 1, lr = hh[h] & 1;
		if (h_ >= m && lr == 1)
			t = update(t, 0, m_, xx[h_ << 1 | 0]);
		tt[h] = t;
	}
	for (int i = 0; i < n; i++) {
		eo_[i] = 2;
		eh[i] = (int *) malloc(eo_[i] * sizeof *eh[i]);
		er[i] = (int *) malloc(eo_[i] * sizeof *er[i]);
	}
	for (int h = 0; h < m_; h++) {
		int h_ = hh[h] >> 1, lr = hh[h] & 1;
		if (h_ < m) {
			if (lr == 0) {
				dp[h_] = query_(ii[h_], h);
				if (dp[h_] != INF)
					dp[h_] += ww[h_];
			} else {
				if (dp[h_] != INF)
					add(jj[h_], h_);
			}
		}
	}
	long long ans = query_(n - 1, m_ - 1);
	return ans == INF ? -1 : ans;
}

Compilation message (stderr)

train.cpp: In function 'long long int solve(int, int, int, vi, vi, vi, vi, vi, vi, vi, vi)':
train.cpp:132:8: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  132 |   xx[m + h << 1 | 0] = ll[h] - 1, xx[m + h << 1 | 1] = rr[h] + 1;
      |      ~~^~~
train.cpp:132:40: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  132 |   xx[m + h << 1 | 0] = ll[h] - 1, xx[m + h << 1 | 1] = rr[h] + 1;
      |                                      ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60