Submission #102105

#	Time	Username	Problem	Language	Result	Execution time	Memory
102105		mzhao	Two Antennas (JOI19_antennas)	C++11	22 / 100	1092 ms	32624 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

#define INF 1000000009
#define MX 200009
#define ll long long
#define x first
#define y second

int N, H[MX], A[MX], B[MX], Q, ans = -1;
vector<int> st[MX], en[MX];
vector<pair<int, int>> ev[MX]; // ev[pos] = {index, s/f}

ll t[2][4*MX]; // min tree   max tree

int clamp(int x) {
	x = min(x, N-1);
	x = max(x, 0);
	return x;
}

int cmp(int z, int a, int b) {
	if (z) return max(a, b);
	return min(a, b);
}

ll up(int z, int n, int a, int b, int x, int v) {
	if (b <= x || x < a) return t[z][n];
	if (a == b-1) {
		t[z][n] = v;
	} else t[z][n] = cmp(z, up(z, 2*n, a, (a+b)/2, x, v), up(z, 2*n+1, (a+b)/2, b, x, v));
	return t[z][n];
}

ll qu(int z, int n, int a, int b, int x, int y) {
	if (b <= x || y <= a) return z ? -INF : INF;
	if (x <= a && b <= y) return t[z][n];
	return cmp(z, qu(z, 2*n, a, (a+b)/2, x, y), qu(z, 2*n+1, (a+b)/2, b, x, y));
}

ll query(int z, int x, int y) {
	x = clamp(x); y = clamp(y);
	ll ret = qu(z, 1, 0, N, x, y+1);
	D("query %d %d %d = %lld\n", z, x, y, ret);
	return ret;
}

void update(int z, int x, int v) {
	D("updating %d %d %d\n", z, x, v);
	up(z, 1, 0, N, x, v);
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d%d", &H[i], &A[i], &B[i]);
		if (i-A[i] >= 0) {
			st[max(i-B[i], 0)].push_back(i);
			en[i-A[i]+1].push_back(i);
		}
		if (i+A[i] < N) {
			st[i+A[i]].push_back(i);
			en[min(i+B[i]+1, N)].push_back(i);
		}
	}
	scanf("%d", &Q);
	assert(Q == 1);
	for (int i = 0; i < N; i++) {
		up(0, 1, 0, N, i, INF);
		up(1, 1, 0, N, i, -INF);
	}
	for (int i = 0; i < N; i++) {
		for (int j : st[i]) {
			update(0, j, H[j]);
			update(1, j, H[j]);
		}
		for (int j : en[i]) {
			update(0, j, INF);
			update(1, j, -INF);
		}
		int minq = min(query(0, i-B[i], i-A[i]), query(0, i+A[i], i+B[i]));
		int maxq = max(query(1, i-B[i], i-A[i]), query(1, i+A[i], i+B[i]));
		if (minq < INF) ans = max(ans, H[i]-minq);
		if (maxq > -INF) ans = max(ans, maxq-H[i]);
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
antennas.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &H[i], &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~

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