Submission #375825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375825	2021-03-10T03:26:36 Z	Kevin_Zhang_TW	Two Antennas (JOI19_antennas)	C++17	13 / 100	105 ms	31472 KB

antennas

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif 
const int MAX_N = 2010, MAX_Q = 200010;

#define int ll

int n, h[MAX_N], a[MAX_N], b[MAX_N];
int q, ql[MAX_Q], qr[MAX_Q], res[MAX_Q];

int ans[MAX_N][MAX_N];
bool valid(int i, int j) {
	if (i == j) return false;
	int dis = abs(j - i);
	return a[i] <= dis && dis <= b[i]
		&& a[j] <= dis && dis <= b[j];
};

void precal() {
	for (int i = 1;i <= n;++i)
		for (int j = i;j <= n;++j) {
			ans[i][j] = -1;
			if (valid(i, j)) {
				DE(i, j);
				ans[i][j] = abs(h[i]-h[j]);
			}
		}

	for (int w = 0;w < n;++w)
		for (int l = 1;l + w <= n;++l) {
			int r = l + w;
			chmax(ans[l-1][r], ans[l][r]);
			chmax(ans[l][r+1], ans[l][r]);
		}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n ;
	for (int i = 1;i <= n;++i)
		cin >> h[i] >> a[i] >> b[i];

	cin >> q;
	for (int i = 1;i <= q;++i) 
		cin >> ql[i] >> qr[i];

	if (n > 2000)  return -1;
		
	precal();

	for (int i = 1;i <= q;++i) 
		res[i] = ans[ ql[i] ][ qr[i] ];

	for (int i = 1;i <= q;++i)
		cout << res[i] << '\n';
}

Compilation message

antennas.cpp: In function 'void precal()':
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
antennas.cpp:37:5: note: in expansion of macro 'DE'
   37 |     DE(i, j);
      |     ^~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	876 KB	Output is correct
2	Correct	2 ms	1900 KB	Output is correct
3	Correct	1 ms	1516 KB	Output is correct
4	Correct	2 ms	2028 KB	Output is correct
5	Correct	1 ms	1644 KB	Output is correct
6	Correct	2 ms	1900 KB	Output is correct
7	Correct	2 ms	1772 KB	Output is correct
8	Correct	2 ms	1900 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	2 ms	1900 KB	Output is correct
11	Correct	1 ms	620 KB	Output is correct
12	Correct	2 ms	1900 KB	Output is correct
13	Correct	1 ms	1772 KB	Output is correct
14	Correct	2 ms	1644 KB	Output is correct
15	Correct	1 ms	1644 KB	Output is correct
16	Correct	1 ms	1644 KB	Output is correct
17	Correct	2 ms	1664 KB	Output is correct
18	Correct	1 ms	1644 KB	Output is correct
19	Correct	1 ms	1644 KB	Output is correct
20	Correct	1 ms	1644 KB	Output is correct
21	Correct	2 ms	1644 KB	Output is correct
22	Correct	2 ms	1644 KB	Output is correct
23	Correct	2 ms	1644 KB	Output is correct
24	Correct	1 ms	1644 KB	Output is correct

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	876 KB	Output is correct
2	Correct	2 ms	1900 KB	Output is correct
3	Correct	1 ms	1516 KB	Output is correct
4	Correct	2 ms	2028 KB	Output is correct
5	Correct	1 ms	1644 KB	Output is correct
6	Correct	2 ms	1900 KB	Output is correct
7	Correct	2 ms	1772 KB	Output is correct
8	Correct	2 ms	1900 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	2 ms	1900 KB	Output is correct
11	Correct	1 ms	620 KB	Output is correct
12	Correct	2 ms	1900 KB	Output is correct
13	Correct	1 ms	1772 KB	Output is correct
14	Correct	2 ms	1644 KB	Output is correct
15	Correct	1 ms	1644 KB	Output is correct
16	Correct	1 ms	1644 KB	Output is correct
17	Correct	2 ms	1664 KB	Output is correct
18	Correct	1 ms	1644 KB	Output is correct
19	Correct	1 ms	1644 KB	Output is correct
20	Correct	1 ms	1644 KB	Output is correct
21	Correct	2 ms	1644 KB	Output is correct
22	Correct	2 ms	1644 KB	Output is correct
23	Correct	2 ms	1644 KB	Output is correct
24	Correct	1 ms	1644 KB	Output is correct
25	Correct	48 ms	11884 KB	Output is correct
26	Correct	37 ms	23788 KB	Output is correct
27	Correct	77 ms	24428 KB	Output is correct
28	Correct	92 ms	31468 KB	Output is correct
29	Correct	46 ms	13804 KB	Output is correct
30	Correct	74 ms	28652 KB	Output is correct
31	Correct	55 ms	9324 KB	Output is correct
32	Correct	103 ms	31472 KB	Output is correct
33	Correct	65 ms	18796 KB	Output is correct
34	Correct	60 ms	27116 KB	Output is correct
35	Correct	84 ms	23168 KB	Output is correct
36	Correct	105 ms	31468 KB	Output is correct
37	Correct	63 ms	26604 KB	Output is correct
38	Correct	87 ms	29676 KB	Output is correct
39	Correct	40 ms	23404 KB	Output is correct
40	Correct	89 ms	29932 KB	Output is correct
41	Correct	80 ms	27756 KB	Output is correct
42	Correct	87 ms	29676 KB	Output is correct
43	Correct	50 ms	24684 KB	Output is correct
44	Correct	87 ms	29676 KB	Output is correct
45	Correct	41 ms	23788 KB	Output is correct
46	Correct	86 ms	29804 KB	Output is correct
47	Correct	47 ms	24300 KB	Output is correct
48	Correct	87 ms	29804 KB	Output is correct

Subtask #3
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	620 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	876 KB	Output is correct
2	Correct	2 ms	1900 KB	Output is correct
3	Correct	1 ms	1516 KB	Output is correct
4	Correct	2 ms	2028 KB	Output is correct
5	Correct	1 ms	1644 KB	Output is correct
6	Correct	2 ms	1900 KB	Output is correct
7	Correct	2 ms	1772 KB	Output is correct
8	Correct	2 ms	1900 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	2 ms	1900 KB	Output is correct
11	Correct	1 ms	620 KB	Output is correct
12	Correct	2 ms	1900 KB	Output is correct
13	Correct	1 ms	1772 KB	Output is correct
14	Correct	2 ms	1644 KB	Output is correct
15	Correct	1 ms	1644 KB	Output is correct
16	Correct	1 ms	1644 KB	Output is correct
17	Correct	2 ms	1664 KB	Output is correct
18	Correct	1 ms	1644 KB	Output is correct
19	Correct	1 ms	1644 KB	Output is correct
20	Correct	1 ms	1644 KB	Output is correct
21	Correct	2 ms	1644 KB	Output is correct
22	Correct	2 ms	1644 KB	Output is correct
23	Correct	2 ms	1644 KB	Output is correct
24	Correct	1 ms	1644 KB	Output is correct
25	Correct	48 ms	11884 KB	Output is correct
26	Correct	37 ms	23788 KB	Output is correct
27	Correct	77 ms	24428 KB	Output is correct
28	Correct	92 ms	31468 KB	Output is correct
29	Correct	46 ms	13804 KB	Output is correct
30	Correct	74 ms	28652 KB	Output is correct
31	Correct	55 ms	9324 KB	Output is correct
32	Correct	103 ms	31472 KB	Output is correct
33	Correct	65 ms	18796 KB	Output is correct
34	Correct	60 ms	27116 KB	Output is correct
35	Correct	84 ms	23168 KB	Output is correct
36	Correct	105 ms	31468 KB	Output is correct
37	Correct	63 ms	26604 KB	Output is correct
38	Correct	87 ms	29676 KB	Output is correct
39	Correct	40 ms	23404 KB	Output is correct
40	Correct	89 ms	29932 KB	Output is correct
41	Correct	80 ms	27756 KB	Output is correct
42	Correct	87 ms	29676 KB	Output is correct
43	Correct	50 ms	24684 KB	Output is correct
44	Correct	87 ms	29676 KB	Output is correct
45	Correct	41 ms	23788 KB	Output is correct
46	Correct	86 ms	29804 KB	Output is correct
47	Correct	47 ms	24300 KB	Output is correct
48	Correct	87 ms	29804 KB	Output is correct
49	Runtime error	4 ms	620 KB	Execution killed with signal 11
50	Halted	0 ms	0 KB	-

Submission #375825

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 11.0 / 11.0

Subtask #3 0 / 22.0

Subtask #4 0 / 65.0

Subtask #1
2.0 / 2.0

Subtask #2
11.0 / 11.0

Subtask #3
0 / 22.0

Subtask #4
0 / 65.0