#include <stdio.h>
#include <string.h>
#define N 50000
#define M 50000
#define K (N + M)
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N], bb[M], cc[K], hh[K], n, m, k;
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 (cc[hh[j]] == cc[h])
j++;
else if (cc[hh[j]] < cc[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;
}
}
long long solve(int i_, int j_) {
static int iil[N], iir[N], jjl[M], jjr[M], iil_[M], iir_[M], jjl_[N], jjr_[N];
static long long dpl[K], dpr[K];
int nl, nr, ml, mr, h, h_, i, j, lower, upper;
long long x, ans;
nl = 0;
for (i = i_; i >= 0; i--)
if (nl == 0 || aa[iil[nl - 1]] < aa[i])
iil[nl++] = i;
nr = 0;
for (i = i_; i < n; i++)
if (nr == 0 || aa[iir[nr - 1]] < aa[i])
iir[nr++] = i;
ml = 0;
for (j = j_; j >= 0; j--)
if (ml == 0 || bb[jjl[ml - 1]] < bb[j])
jjl[ml++] = j;
mr = 0;
for (j = j_; j < m; j++)
if (mr == 0 || bb[jjr[mr - 1]] < bb[j])
jjr[mr++] = j;
for (i = 0; i < n; i++) {
lower = -1, upper = ml;
while (upper - lower > 1) {
j = (lower + upper) / 2;
if (bb[jjl[j]] > aa[i])
upper = j;
else
lower = j;
}
jjl_[i] = upper == ml ? -1 : jjl[upper];
lower = -1, upper = mr;
while (upper - lower > 1) {
j = (lower + upper) / 2;
if (bb[jjr[j]] > aa[i])
upper = j;
else
lower = j;
}
jjr_[i] = upper == mr ? -1 : jjr[upper];
}
for (j = 0; j < m; j++) {
lower = -1, upper = nl;
while (upper - lower > 1) {
i = (lower + upper) / 2;
if (aa[iil[i]] > bb[j])
upper = i;
else
lower = i;
}
iil_[j] = upper == nl ? -1 : iil[upper];
lower = -1, upper = nr;
while (upper - lower > 1) {
i = (lower + upper) / 2;
if (aa[iir[i]] > bb[j])
upper = i;
else
lower = i;
}
iir_[j] = upper == nr ? -1 : iir[upper];
}
memset(dpl, -1, k * sizeof *dpl), memset(dpr, -1, k * sizeof *dpr);
if (aa[i_] > bb[j_])
dpl[n + j_] = 0;
else
dpl[i_] = 0;
ans = 0;
for (h = 0; h < k; h++) {
h_ = hh[h];
if (h_ < n)
i = h_;
else
j = h_ - n;
if (h_ < n) {
if ((x = dpl[h_]) != -1) {
j = jjl_[i];
if ((i_ = iil_[j]) == -1)
ans = max(ans, x + i);
else
dpl[n + j] = max(dpl[n + j], x + i - i_);
if ((i_ = iir_[j]) == -1)
ans = max(ans, x + n - 1 - i);
else
dpr[n + j] = max(dpr[n + j], x + i_ - i);
}
if ((x = dpr[h_]) != -1) {
j = jjr_[i];
if ((i_ = iil_[j]) == -1)
ans = max(ans, x + i);
else
dpl[n + j] = max(dpl[n + j], x + i - i_);
if ((i_ = iir_[j]) == -1)
ans = max(ans, x + n - 1 - i);
else
dpr[n + j] = max(dpr[n + j], x + i_ - i);
}
} else {
if ((x = dpl[h_]) != -1) {
i = iil_[j];
if ((j_ = jjl_[i]) == -1)
ans = max(ans, x + j);
else
dpl[i] = max(dpl[i], x + j - j_);
if ((j_ = jjr_[i]) == -1)
ans = max(ans, x + m - 1 - j);
else
dpr[i] = max(dpr[i], x + j_ - j);
}
if ((x = dpr[h_]) != -1) {
i = iir_[j];
if ((j_ = jjl_[i]) == -1)
ans = max(ans, x + j);
else
dpl[i] = max(dpl[i], x + j - j_);
if ((j_ = jjr_[i]) == -1)
ans = max(ans, x + m - 1 - j);
else
dpr[i] = max(dpr[i], x + j_ - j);
}
}
}
return ans;
}
int main() {
int q, h, i, j;
scanf("%d%d%d", &n, &m, &q), k = n + m;
for (i = 0; i < n; i++)
scanf("%d", &aa[i]);
for (j = 0; j < m; j++)
scanf("%d", &bb[j]);
for (h = 0; h < k; h++)
cc[h] = h < n ? aa[h] : bb[h - n];
for (h = 0; h < k; h++)
hh[h] = h;
sort(hh, 0, k);
while (q--) {
int i, i_, j, j_;
long long ans;
scanf("%d%d", &i, &j), i--, j--;
ans = -1;
i_ = i - 1;
while (i_ >= 0 && aa[i_] < bb[j])
i_--;
if (i_ < 0)
ans = max(ans, i);
else
ans = max(ans, i - i_ + solve(i_, j));
i_ = i + 1;
while (i_ < n && aa[i_] < bb[j])
i_++;
if (i_ >= n)
ans = max(ans, n - 1 - i);
else
ans = max(ans, i_ - i + solve(i_, j));
j_ = j - 1;
while (j_ >= 0 && bb[j_] < aa[i])
j_--;
if (j_ < 0)
ans = max(ans, j);
else
ans = max(ans, j - j_ + solve(i, j_));
j_ = j + 1;
while (j_ < m && bb[j_] < aa[i])
j_++;
if (j_ >= m)
ans = max(ans, m - 1 - j);
else
ans = max(ans, j_ - j + solve(i, j_));
printf("%lld\n", ans);
}
return 0;
}
Compilation message
abduction2.c: In function 'main':
abduction2.c:165:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%d%d%d", &n, &m, &q), k = n + m;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
abduction2.c:167:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
abduction2.c:169:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d", &bb[j]);
| ^~~~~~~~~~~~~~~~~~~
abduction2.c:179:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
292 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
292 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
296 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
436 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
3 ms |
468 KB |
Output is correct |
20 |
Correct |
3 ms |
468 KB |
Output is correct |
21 |
Correct |
4 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
292 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
296 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
436 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
3 ms |
468 KB |
Output is correct |
20 |
Correct |
3 ms |
468 KB |
Output is correct |
21 |
Correct |
4 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
436 KB |
Output is correct |
23 |
Correct |
42 ms |
4768 KB |
Output is correct |
24 |
Correct |
43 ms |
4748 KB |
Output is correct |
25 |
Correct |
40 ms |
4768 KB |
Output is correct |
26 |
Correct |
46 ms |
4720 KB |
Output is correct |
27 |
Correct |
43 ms |
4772 KB |
Output is correct |
28 |
Correct |
51 ms |
5040 KB |
Output is correct |
29 |
Correct |
55 ms |
4868 KB |
Output is correct |
30 |
Correct |
86 ms |
4924 KB |
Output is correct |
31 |
Correct |
90 ms |
5052 KB |
Output is correct |
32 |
Correct |
65 ms |
4784 KB |
Output is correct |
33 |
Correct |
71 ms |
4828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
468 KB |
Output is correct |
2 |
Correct |
46 ms |
468 KB |
Output is correct |
3 |
Correct |
46 ms |
516 KB |
Output is correct |
4 |
Correct |
41 ms |
512 KB |
Output is correct |
5 |
Correct |
42 ms |
512 KB |
Output is correct |
6 |
Correct |
75 ms |
528 KB |
Output is correct |
7 |
Correct |
66 ms |
544 KB |
Output is correct |
8 |
Correct |
126 ms |
540 KB |
Output is correct |
9 |
Correct |
132 ms |
468 KB |
Output is correct |
10 |
Correct |
138 ms |
532 KB |
Output is correct |
11 |
Correct |
146 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
292 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
296 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
436 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
3 ms |
468 KB |
Output is correct |
20 |
Correct |
3 ms |
468 KB |
Output is correct |
21 |
Correct |
4 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
436 KB |
Output is correct |
23 |
Correct |
42 ms |
4768 KB |
Output is correct |
24 |
Correct |
43 ms |
4748 KB |
Output is correct |
25 |
Correct |
40 ms |
4768 KB |
Output is correct |
26 |
Correct |
46 ms |
4720 KB |
Output is correct |
27 |
Correct |
43 ms |
4772 KB |
Output is correct |
28 |
Correct |
51 ms |
5040 KB |
Output is correct |
29 |
Correct |
55 ms |
4868 KB |
Output is correct |
30 |
Correct |
86 ms |
4924 KB |
Output is correct |
31 |
Correct |
90 ms |
5052 KB |
Output is correct |
32 |
Correct |
65 ms |
4784 KB |
Output is correct |
33 |
Correct |
71 ms |
4828 KB |
Output is correct |
34 |
Correct |
40 ms |
468 KB |
Output is correct |
35 |
Correct |
46 ms |
468 KB |
Output is correct |
36 |
Correct |
46 ms |
516 KB |
Output is correct |
37 |
Correct |
41 ms |
512 KB |
Output is correct |
38 |
Correct |
42 ms |
512 KB |
Output is correct |
39 |
Correct |
75 ms |
528 KB |
Output is correct |
40 |
Correct |
66 ms |
544 KB |
Output is correct |
41 |
Correct |
126 ms |
540 KB |
Output is correct |
42 |
Correct |
132 ms |
468 KB |
Output is correct |
43 |
Correct |
138 ms |
532 KB |
Output is correct |
44 |
Correct |
146 ms |
468 KB |
Output is correct |
45 |
Correct |
1214 ms |
4756 KB |
Output is correct |
46 |
Correct |
1293 ms |
4772 KB |
Output is correct |
47 |
Correct |
1245 ms |
4848 KB |
Output is correct |
48 |
Correct |
1186 ms |
4772 KB |
Output is correct |
49 |
Correct |
1233 ms |
4776 KB |
Output is correct |
50 |
Correct |
2591 ms |
5200 KB |
Output is correct |
51 |
Correct |
2620 ms |
5152 KB |
Output is correct |
52 |
Execution timed out |
5022 ms |
5304 KB |
Time limit exceeded |
53 |
Halted |
0 ms |
0 KB |
- |