oj.uz

Submission #708515

# Submission time Handle Problem Language Result Execution time Memory
708515 2023-03-11T23:41:15 Z rainboy Dungeon 3 (JOI21_ho_t5) C
100 / 100
 948 ms 40928 KB 
/* https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t5-review.pdf */
#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N))) */
#define N4	(N * 4 + 1)
#define M	200000

int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

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

int dd[N], cc[N], kk[N], n; long long xx[N + 1];
int ll[M], ll1[M * 2], rr[M], tt[M], m; long long ans[M];

int st[N_ * 2], n_;

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		st[n_ + i] = aa[i];
	for (i = n_ - 1; i > 0; i--)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

int st_query(int l, int r) {
	int x;

	x = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x = max(x, st[l++]);
		if ((r & 1) == 0)
			x = max(x, st[r--]);
	}
	return x;
}

int *vv;

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)
			if (vv[hh[j]] == vv[h])
				j++;
			else if (vv[hh[j]] < vv[h]) {
				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 zz[N4], ll_[N4], rr_[N4], u_, l_, r_; long long xx_[N4], aa[N4], aa_[N4], bb[N4], bb_[N4];

int node(long long x, long long a, long long b) {
	static int _ = 1;

	zz[_] = rand_();
	xx_[_] = x, aa_[_] = aa[_] = a, bb_[_] = bb[_] = b;
	return _++;
}

void pul(int u) {
	int l = ll_[u], r = rr_[u];

	aa_[u] = aa_[l] + aa[u] + aa_[r], bb_[u] = bb_[l] + bb[u] + bb_[r];
}

void split(int u, long long x) {
	if (u == 0) {
		u_ = u, l_ = r_ = 0;
		return;
	}
	if (xx_[u] < x) {
		split(rr_[u], x);
		rr_[u] = l_, l_ = u;
	} else if (xx_[u] > x) {
		split(ll_[u], x);
		ll_[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll_[u], r_ = rr_[u];
		ll_[u] = rr_[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr_[u] = merge(rr_[u], v), pul(u);
		return u;
	} else {
		ll_[v] = merge(u, ll_[v]), pul(v);
		return v;
	}
}

void tr_update(long long x, long long a, long long b) {
	split(u_, x);
	if (u_ == 0)
		u_ = node(x, a, b);
	else
		aa_[u_] = aa[u_] += a, bb_[u_] = bb[u_] += b;
	u_ = merge(merge(l_, u_), r_);
}

long long tr_query(long long x) {
	int u;
	long long a, b;

	u = u_, a = 0, b = 0;
	while (u)
		if (xx_[u] <= x)
			a += aa_[u] - aa_[rr_[u]], b += bb_[u] - bb_[rr_[u]], u = rr_[u];
		else
			u = ll_[u];
	return a * x + b;
}

int main() {
	static int qu[N], hh[M], hh_[M * 2];
	int m_, cnt, g, h, h_, i, j, lower, upper;

	scanf("%d%d", &n, &m);
	xx[0] = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &dd[i]);
		xx[i + 1] = xx[i] + dd[i];
	}
	build(dd, n);
	for (i = 0; i < n; i++)
		scanf("%d", &cc[i]);
	for (h = 0; h < m; h++)
		scanf("%d%d%d", &ll[h], &rr[h], &tt[h]), ll[h]--, rr[h]--;
	for (h = 0; h < m; h++)
		hh[h] = h;
	vv = rr, sort(hh, 0, m);
	cnt = 0, m_ = 0;
	for (h = 0, i = 0; i <= n; i++) {
		while (h < m && rr[h_ = hh[h]] == i) {
			if (tt[h_] < st_query(ll[h_], rr[h_] - 1))
				ans[h_] = -1;
			else {
				lower = -1, upper = cnt - 1;
				while (upper - lower > 1) {
					g = (lower + upper) / 2;
					if (qu[g] >= ll[h_] && xx[i] - xx[qu[g]] <= tt[h_])
						upper = g;
					else
						lower = g;
				}
				g = upper;
				ans[h_] += (xx[i] - xx[qu[g]]) * cc[qu[g]];
				ll1[h_ << 1 | 0] = ll[h_], hh_[m_++] = h_ << 1 | 0;
				ll1[h_ << 1 | 1] = qu[g], hh_[m_++] = h_ << 1 | 1;
			}
			h++;
		}
		if (i < n) {
			while (cnt && cc[qu[cnt - 1]] > cc[i])
				cnt--;
			qu[cnt++] = i;
		}
	}
	vv = ll1, sort(hh_, 0, m_);
	cnt = 0;
	for (i = n, h = m_ - 1; i >= 0; i--) {
		if (i < n) {
			while (cnt && cc[j = qu[cnt - 1]] >= cc[i]) {
				tr_update(xx[j] - xx[i], -cc[j], (xx[j] - xx[i]) * cc[j]);
				tr_update(xx[kk[j]] - xx[i], cc[j], -(xx[kk[j]] - xx[i]) * cc[j]);
				cnt--;
			}
			kk[i] = cnt == 0 ? n : qu[cnt - 1];
			tr_update(0, cc[i], 0);
			tr_update(xx[kk[i]] - xx[i], -cc[i], (xx[kk[i]] - xx[i]) * cc[i]);
			qu[cnt++] = i;
		}
		while (h >= 0 && ll1[h_ = hh_[h]] == i) {
			ans[h_ >> 1] += tr_query(tt[h_ >> 1]) * ((h_ & 1) == 0 ? 1 : -1);
			h--;
		}
	}
	for (h = 0; h < m; h++)
		printf("%lld\n", ans[h]);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:142:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:145:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |   scanf("%d", &dd[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:150:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d", &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d%d", &ll[h], &rr[h], &tt[h]), ll[h]--, rr[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 852 KB Output is correct
2 Correct 6 ms 996 KB Output is correct
3 Correct 4 ms 816 KB Output is correct
4 Correct 8 ms 940 KB Output is correct
5 Correct 6 ms 940 KB Output is correct
6 Correct 5 ms 816 KB Output is correct
7 Correct 7 ms 944 KB Output is correct
8 Correct 7 ms 1008 KB Output is correct
9 Correct 5 ms 752 KB Output is correct
10 Correct 10 ms 980 KB Output is correct
11 Correct 8 ms 1076 KB Output is correct
12 Correct 6 ms 820 KB Output is correct
13 Correct 8 ms 944 KB Output is correct
14 Correct 6 ms 980 KB Output is correct
15 Correct 6 ms 980 KB Output is correct
16 Correct 7 ms 944 KB Output is correct
17 Correct 7 ms 816 KB Output is correct
18 Correct 8 ms 852 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 5 ms 852 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 9452 KB Output is correct
2 Correct 152 ms 10596 KB Output is correct
3 Correct 142 ms 11096 KB Output is correct
4 Correct 100 ms 8504 KB Output is correct
5 Correct 218 ms 10692 KB Output is correct
6 Correct 438 ms 40176 KB Output is correct
7 Correct 641 ms 36804 KB Output is correct
8 Correct 873 ms 40928 KB Output is correct
9 Correct 569 ms 31004 KB Output is correct
10 Correct 636 ms 33860 KB Output is correct
11 Correct 597 ms 33432 KB Output is correct
12 Correct 427 ms 24056 KB Output is correct
13 Correct 664 ms 25164 KB Output is correct
14 Correct 650 ms 25208 KB Output is correct
15 Correct 386 ms 32380 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 24484 KB Output is correct
2 Correct 671 ms 29748 KB Output is correct
3 Correct 484 ms 23812 KB Output is correct
4 Correct 752 ms 30436 KB Output is correct
5 Correct 401 ms 33324 KB Output is correct
6 Correct 633 ms 29168 KB Output is correct
7 Correct 489 ms 16880 KB Output is correct
8 Correct 418 ms 26284 KB Output is correct
9 Correct 232 ms 16628 KB Output is correct
10 Correct 365 ms 27596 KB Output is correct
11 Correct 560 ms 33036 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 852 KB Output is correct
2 Correct 6 ms 996 KB Output is correct
3 Correct 4 ms 816 KB Output is correct
4 Correct 8 ms 940 KB Output is correct
5 Correct 6 ms 940 KB Output is correct
6 Correct 5 ms 816 KB Output is correct
7 Correct 7 ms 944 KB Output is correct
8 Correct 7 ms 1008 KB Output is correct
9 Correct 5 ms 752 KB Output is correct
10 Correct 10 ms 980 KB Output is correct
11 Correct 8 ms 1076 KB Output is correct
12 Correct 6 ms 820 KB Output is correct
13 Correct 8 ms 944 KB Output is correct
14 Correct 6 ms 980 KB Output is correct
15 Correct 6 ms 980 KB Output is correct
16 Correct 7 ms 944 KB Output is correct
17 Correct 7 ms 816 KB Output is correct
18 Correct 8 ms 852 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 5 ms 852 KB Output is correct
21 Correct 113 ms 9452 KB Output is correct
22 Correct 152 ms 10596 KB Output is correct
23 Correct 142 ms 11096 KB Output is correct
24 Correct 100 ms 8504 KB Output is correct
25 Correct 218 ms 10692 KB Output is correct
26 Correct 438 ms 40176 KB Output is correct
27 Correct 641 ms 36804 KB Output is correct
28 Correct 873 ms 40928 KB Output is correct
29 Correct 569 ms 31004 KB Output is correct
30 Correct 636 ms 33860 KB Output is correct
31 Correct 597 ms 33432 KB Output is correct
32 Correct 427 ms 24056 KB Output is correct
33 Correct 664 ms 25164 KB Output is correct
34 Correct 650 ms 25208 KB Output is correct
35 Correct 386 ms 32380 KB Output is correct
36 Correct 948 ms 24484 KB Output is correct
37 Correct 671 ms 29748 KB Output is correct
38 Correct 484 ms 23812 KB Output is correct
39 Correct 752 ms 30436 KB Output is correct
40 Correct 401 ms 33324 KB Output is correct
41 Correct 633 ms 29168 KB Output is correct
42 Correct 489 ms 16880 KB Output is correct
43 Correct 418 ms 26284 KB Output is correct
44 Correct 232 ms 16628 KB Output is correct
45 Correct 365 ms 27596 KB Output is correct
46 Correct 560 ms 33036 KB Output is correct
47 Correct 757 ms 24988 KB Output is correct
48 Correct 909 ms 40420 KB Output is correct
49 Correct 375 ms 23376 KB Output is correct
50 Correct 910 ms 37084 KB Output is correct
51 Correct 408 ms 33196 KB Output is correct
52 Correct 600 ms 33404 KB Output is correct
53 Correct 590 ms 23180 KB Output is correct
54 Correct 547 ms 32908 KB Output is correct
55 Correct 298 ms 22828 KB Output is correct
56 Correct 375 ms 33356 KB Output is correct
57 Correct 630 ms 39604 KB Output is correct