oj.uz

Submission #1061627

# Submission time Handle Problem Language Result Execution time Memory
1061627 2024-08-16T11:19:11 Z rainboy Train (APIO24_train) C++17
100 / 100
 530 ms 56436 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Correct.
2 Correct 2 ms 8540 KB Correct.
3 Correct 2 ms 8540 KB Correct.
4 Correct 1 ms 8540 KB Correct.
5 Correct 1 ms 4444 KB Correct.
6 Correct 1 ms 8540 KB Correct.
7 Correct 1 ms 8540 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15504 KB Correct.
2 Correct 91 ms 22256 KB Correct.
3 Correct 1 ms 4444 KB Correct.
4 Correct 17 ms 11868 KB Correct.
5 Correct 1 ms 8540 KB Correct.
6 Correct 81 ms 14784 KB Correct.
7 Correct 1 ms 8540 KB Correct.
8 Correct 75 ms 22224 KB Correct.
9 Correct 93 ms 22336 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15504 KB Correct.
2 Correct 91 ms 22256 KB Correct.
3 Correct 1 ms 4444 KB Correct.
4 Correct 17 ms 11868 KB Correct.
5 Correct 1 ms 8540 KB Correct.
6 Correct 81 ms 14784 KB Correct.
7 Correct 1 ms 8540 KB Correct.
8 Correct 75 ms 22224 KB Correct.
9 Correct 93 ms 22336 KB Correct.
10 Correct 524 ms 42912 KB Correct.
11 Correct 286 ms 56180 KB Correct.
12 Correct 13 ms 12380 KB Correct.
13 Correct 1 ms 4700 KB Correct.
14 Correct 445 ms 47136 KB Correct.
15 Correct 286 ms 56396 KB Correct.
16 Correct 441 ms 47456 KB Correct.
17 Correct 259 ms 55404 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Correct.
2 Correct 2 ms 8540 KB Correct.
3 Correct 2 ms 8540 KB Correct.
4 Correct 1 ms 8540 KB Correct.
5 Correct 1 ms 4444 KB Correct.
6 Correct 1 ms 8540 KB Correct.
7 Correct 1 ms 8540 KB Correct.
8 Correct 89 ms 15504 KB Correct.
9 Correct 91 ms 22256 KB Correct.
10 Correct 1 ms 4444 KB Correct.
11 Correct 17 ms 11868 KB Correct.
12 Correct 1 ms 8540 KB Correct.
13 Correct 81 ms 14784 KB Correct.
14 Correct 1 ms 8540 KB Correct.
15 Correct 75 ms 22224 KB Correct.
16 Correct 93 ms 22336 KB Correct.
17 Correct 524 ms 42912 KB Correct.
18 Correct 286 ms 56180 KB Correct.
19 Correct 13 ms 12380 KB Correct.
20 Correct 1 ms 4700 KB Correct.
21 Correct 445 ms 47136 KB Correct.
22 Correct 286 ms 56396 KB Correct.
23 Correct 441 ms 47456 KB Correct.
24 Correct 259 ms 55404 KB Correct.
25 Correct 305 ms 56432 KB Correct.
26 Correct 280 ms 56436 KB Correct.
27 Correct 336 ms 56404 KB Correct.
28 Correct 315 ms 56436 KB Correct.
29 Correct 501 ms 48792 KB Correct.
30 Correct 470 ms 47700 KB Correct.
31 Correct 501 ms 47684 KB Correct.
32 Correct 482 ms 47560 KB Correct.
33 Correct 474 ms 47276 KB Correct.
34 Correct 458 ms 47248 KB Correct.
35 Correct 447 ms 47444 KB Correct.
36 Correct 530 ms 47688 KB Correct.
37 Correct 330 ms 56436 KB Correct.
38 Correct 476 ms 47588 KB Correct.
39 Correct 430 ms 47188 KB Correct.
40 Correct 295 ms 56404 KB Correct.
41 Correct 142 ms 53620 KB Correct.
42 Correct 112 ms 46416 KB Correct.
43 Correct 366 ms 45492 KB Correct.
44 Correct 279 ms 56188 KB Correct.
45 Correct 312 ms 56224 KB Correct.
46 Correct 266 ms 56240 KB Correct.
47 Correct 365 ms 55224 KB Correct.
48 Correct 271 ms 54868 KB Correct.
49 Correct 263 ms 54868 KB Correct.
50 Correct 269 ms 54772 KB Correct.
51 Correct 205 ms 54868 KB Correct.
52 Correct 236 ms 54896 KB Correct.