oj.uz

Submission #102105

# Submission time Handle Problem Language Result Execution time Memory
102105 2019-03-22T11:08:26 Z mzhao Two Antennas (JOI19_antennas) C++11
22 / 100
 1092 ms 32624 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 28800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 28800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 31488 KB Output is correct
2 Correct 1070 ms 32392 KB Output is correct
3 Correct 647 ms 29584 KB Output is correct
4 Correct 990 ms 32496 KB Output is correct
5 Correct 411 ms 23364 KB Output is correct
6 Correct 1010 ms 32468 KB Output is correct
7 Correct 764 ms 31088 KB Output is correct
8 Correct 953 ms 32488 KB Output is correct
9 Correct 102 ms 17400 KB Output is correct
10 Correct 1092 ms 32340 KB Output is correct
11 Correct 562 ms 24696 KB Output is correct
12 Correct 1026 ms 32624 KB Output is correct
13 Correct 448 ms 29300 KB Output is correct
14 Correct 523 ms 29036 KB Output is correct
15 Correct 544 ms 28276 KB Output is correct
16 Correct 558 ms 28400 KB Output is correct
17 Correct 552 ms 29804 KB Output is correct
18 Correct 501 ms 29044 KB Output is correct
19 Correct 618 ms 28508 KB Output is correct
20 Correct 468 ms 28612 KB Output is correct
21 Correct 472 ms 29224 KB Output is correct
22 Correct 506 ms 29040 KB Output is correct
23 Correct 526 ms 28880 KB Output is correct
24 Correct 495 ms 28020 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 28800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -