Submission #309609

#TimeUsernameProblemLanguageResultExecution timeMemory
309609luciocfAbduction 2 (JOI17_abduction2)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e4+10; const int maxl = 18; int n, m; int a[2][maxn]; map<int, ll> dp[maxn][2]; struct SparseTable { int tab[2][2][maxn][maxl]; void build(void) { for (int i = 1; i <= n; i++) { if (i > 1) tab[0][0][i][0] = a[0][i-1]; if (i < n) tab[0][1][i][0] = a[0][i+1]; } for (int i = 1; i <= m; i++) { if (i > 1) tab[1][0][i][0] = a[1][i-1]; if (i < m) tab[1][1][i][0] = a[1][i+1]; } for (int j = 1; j < maxl; j++) { for (int i = 1; i <= n; i++) { if (i-(1<<j) > 0) tab[0][0][i][j] = max(tab[0][0][i][j-1], tab[0][0][i-(1<<(j-1))][j-1]); if (i+(1<<j) <= n) tab[0][1][i][j] = max(tab[0][1][i][j-1], tab[0][1][i+(1<<(j-1))][j-1]); } for (int i = 1; i <= m; i++) { if (i-(1<<j) > 0) tab[1][0][i][j] = max(tab[1][0][i][j-1], tab[1][0][i-(1<<(j-1))][j-1]); if (i+(1<<j) <= m) tab[1][1][i][j] = max(tab[1][1][i][j-1], tab[1][1][i+(1<<(j-1))][j-1]); } } } int get_l(int pos, int x, int q) { for (int i = maxl-1; i >= 0; i--) if (pos-(1<<i) > 0 && tab[q][0][pos][i] < x) pos -= (1<<i); return pos-1; } int get_r(int pos, int x, int q) { for (int i = maxl-1; i >= 0; i--) if (pos+(1<<i) <= (!q ? n : m) && tab[q][1][pos][i] < x) pos += (1<<i); return pos+1; } } ST; ll solve(int i, int j, int q) { if (dp[i][q].find(j) != dp[i][q].end()) return dp[i][q][j]; ll ans; if (!q) { int l = ST.get_l(j, a[0][i], 1), r = ST.get_r(j, a[0][i], 1); if (l == 0 && r == m+1) ans = max(j-1, m-j); else if (l == 0) ans = max({1ll*(j-1), (1ll*(r-j) + solve(i, r, 1))}); else if (r == m+1) ans = max({1ll*(m-j), (1ll*(j-l) + solve(i, l, 1))}); else ans = max(1ll*(r-j) + solve(i, r, 1), 1ll*(j-l) + solve(i, l, 1)); } else { int l = ST.get_l(i, a[1][j], 0), r = ST.get_r(i, a[1][j], 0); if (l == 0 && r == n+1) ans = max(i-1, n-i); else if (l == 0) ans = max({1ll*(i-1), 1ll*(r-i) + solve(r, j, 0)}); else if (r == n+1) ans = max(1ll*(n-i), (1ll*(i-l) + solve(l, j, 0))}); else ans = max(1ll*(r-i) + solve(r, j, 0), 1ll*(i-l) + solve(l, j, 0)); } return dp[i][q][j] = ans; } int main(void) { int q; scanf("%d %d %d", &n, &m, &q); for (int i = 1; i <= n; i++) scanf("%d", &a[0][i]); for (int i = 1; i <= m; i++) scanf("%d", &a[1][i]); ST.build(); while (q--) { int i, j; scanf("%d %d", &i, &j); printf("%lld\n", max(solve(i, j, 0), solve(i, j, 1))); } }

Compilation message (stderr)

abduction2.cpp: In function 'll solve(int, int, int)':
abduction2.cpp:97:71: error: expected ')' before '}' token
   97 |   else if (r == n+1) ans = max(1ll*(n-i), (1ll*(i-l) + solve(l, j, 0))});
      |                               ~                                       ^
      |                                                                       )
abduction2.cpp:97:72: error: expected primary-expression before ')' token
   97 |   else if (r == n+1) ans = max(1ll*(n-i), (1ll*(i-l) + solve(l, j, 0))});
      |                                                                        ^
abduction2.cpp:98:3: error: 'else' without a previous 'if'
   98 |   else ans = max(1ll*(r-i) + solve(r, j, 0), 1ll*(i-l) + solve(l, j, 0));
      |   ^~~~
abduction2.cpp:98:23: error: 'r' was not declared in this scope
   98 |   else ans = max(1ll*(r-i) + solve(r, j, 0), 1ll*(i-l) + solve(l, j, 0));
      |                       ^
abduction2.cpp:98:53: error: 'l' was not declared in this scope
   98 |   else ans = max(1ll*(r-i) + solve(r, j, 0), 1ll*(i-l) + solve(l, j, 0));
      |                                                     ^
abduction2.cpp: At global scope:
abduction2.cpp:101:2: error: expected unqualified-id before 'return'
  101 |  return dp[i][q][j] = ans;
      |  ^~~~~~
abduction2.cpp:102:1: error: expected declaration before '}' token
  102 | }
      | ^
abduction2.cpp: In function 'll solve(int, int, int)':
abduction2.cpp:99:2: warning: control reaches end of non-void function [-Wreturn-type]
   99 |  }
      |  ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   scanf("%d", &a[0][i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |   scanf("%d", &a[1][i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |   scanf("%d %d", &i, &j);
      |   ~~~~~^~~~~~~~~~~~~~~~~