Submission #684217

#TimeUsernameProblemLanguageResultExecution timeMemory
684217rainboyAbduction 2 (JOI17_abduction2)C11
100 / 100
860 ms5144 KiB
#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, il, ir, j, jl, jr; 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 (h = 0, il = ir = 0, jl = jr = 0; h < n + m; h++) { h_ = hh[h]; if (h_ < n) { i = h_; while (jl < ml && bb[jjl[jl]] < cc[h_]) jl++; while (jr < mr && bb[jjr[jr]] < cc[h_]) jr++; jjl_[i] = jl == ml ? -1 : jjl[jl], jjr_[i] = jr == mr ? -1 : jjr[jr]; } else { j = h_ - n; while (il < nl && aa[iil[il]] < cc[h_]) il++; while (ir < nr && aa[iir[ir]] < cc[h_]) ir++; iil_[j] = il == nl ? -1 : iil[il], iir_[j] = ir == nr ? -1 : iir[ir]; } } 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 (stderr)

abduction2.c: In function 'main':
abduction2.c:143:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  scanf("%d%d%d", &n, &m, &q), k = n + m;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
abduction2.c:145:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
abduction2.c:147:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%d", &bb[j]);
      |   ^~~~~~~~~~~~~~~~~~~
abduction2.c:157:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...