제출 #557205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557205		lunchbox	Two Antennas (JOI19_antennas)	C++17	100 / 100	579 ms	36888 KiB

antennas

/*
https://oj.uz/problem/view/JOI19_antennas
Two Antennas
*/
#include <bits/stdc++.h>
using namespace std;

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N)) */
#define Q	200000
#define INF	0x3f3f3f3f

int st[N_ * 2], mx[N_ * 2], lz[N_ * 2];

void put(int i, int x) {
	lz[i] = max(lz[i], x);
	mx[i] = max(mx[i], lz[i] - st[i]);
}

void pus(int i) {
	if (lz[i] != -INF) {
		put(i << 1 | 0, lz[i]);
		put(i << 1 | 1, lz[i]);
		lz[i] = -INF;
	}
}

void pul(int i) {
	int l = i << 1 | 0, r = i << 1 | 1;

	st[i] = min(st[l], st[r]);
	mx[i] = max(mx[l], mx[r]);
}

void update(int u, int l, int r, int ql, int qr, int x) {
	int m;

	if (qr < l || ql > r)
		assert(0);
	if (ql <= l && qr >= r) {
		put(u, x);
		return;
	}
	pus(u);
	m = (l + r) >> 1;
	if (ql <= m)
		update(u << 1 | 0, l, m, ql, qr, x);
	if (m < qr)
		update(u << 1 | 1, m + 1, r, ql, qr, x);
	pul(u);
}

void update_point(int u, int l, int r, int i, int x) {
	int m;

	if (l == r) {
		st[u] = x;
		lz[u] = -INF;
		return;
	}
	pus(u);
	m = (l + r) >> 1;
	if (i <= m)
		update_point(u << 1 | 0, l, m, i, x);
	else
		update_point(u << 1 | 1, m + 1, r, i, x);
	pul(u);
}

int query(int u, int l, int r, int ql, int qr) {
	int m, x;

	if (qr < l || ql > r)
		assert(0);
	if (ql <= l && qr >= r)
		return mx[u];
	pus(u);
	m = (l + r) >> 1, x = -1;
	if (ql <= m)
		x = max(x, query(u << 1 | 0, l, m, ql, qr));
	if (m < qr)
		x = max(x, query(u << 1 | 1, m + 1, r, ql, qr));
	return x;
}

vector<array<int, 2>> ev[N + 1], qq[N];
int hh[N], aa[N], bb[N], ans[Q], n, n_;

void solve() {
	memset(st, 0x3f, n_ * 2 * sizeof * st);
	memset(mx, -1, n_ * 2 * sizeof * mx);
	memset(lz, -0x3f, n_ * 2 * sizeof * lz);
	for (int i = 0; i < n; i++) {
		for (auto [j, t] : ev[i]) {
			if (t == +1)
				update_point(1, 0, n - 1, j, hh[j]);
			else
				update_point(1, 0, n - 1, j, INF);
		}
		if (i - aa[i] >= 0)
			update(1, 0, n - 1, max(0, i - bb[i]), i - aa[i], hh[i]);
		for (auto [j, h] : qq[i]) {
			int x = query(1, 0, n - 1, j, i);

			ans[h] = max(ans[h], x);
		}
	}
}

int main() {
	int q;

	scanf("%d", &n);
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &hh[i], &aa[i], &bb[i]);
		ev[min(n, i + aa[i])].push_back({ i, +1 });
		ev[min(n, i + bb[i] + 1)].push_back({ i, -1 });
	}
	scanf("%d", &q);
	memset(ans, -1, q * sizeof * ans);
	for (int h = 0; h < q; h++) {
		int l, r;

		scanf("%d%d", &l, &r), l--, r--;
		qq[r].push_back({l, h});
	}
	solve();
	for (int i = 0; i < n; i++)
		hh[i] *= -1;
	solve();
	for (int h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'int main()':
antennas.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
antennas.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d%d%d", &hh[i], &aa[i], &bb[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
antennas.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |   scanf("%d%d", &l, &r), l--, r--;
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65