Submission #464564

#TimeUsernameProblemLanguageResultExecution timeMemory
464564SamAndExam (eJOI20_exam)C++17
13 / 100
826 ms161652 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 100005, N0 = 5003; int n; int a[N], b[N]; int maxi[N0][N0]; vector<int> v[N]; void rec0(int l, int r, int p) { if (l > r) return; int m = maxi[l][r]; rec0(l, m - 1, m); rec0(m + 1, r, m); if (p == 0) return; else if (p == l - 1) { for (int i = l; i <= r; ++i) { if (b[i] == a[p]) v[m].push_back(i); } } else if (p == r + 1) { for (int i = r; i >= l; --i) { if (b[i] == a[p]) v[m].push_back(i); } reverse(all(v[m])); } else assert(false); } int dp[N0 * N0]; bool c[N0 * N0]; int rec(int l, int r, int ul, int ur, int p) { if (l > r) return 0; ul = max(ul, l - 1); ur = min(ur, r + 1); if (ul + 1 >= ur) return 0; int m = maxi[l][r]; ll h = ul * 1LL * N0 * N0 + m * 1LL * N0 + ur; if (c[h]) return dp[h]; c[h] = true; if (ul < m && m < ur && a[m] == b[m]) dp[h] = rec(l, m - 1, ul, ur, m) + rec(m + 1, r, ul, ur, m) + 1; else dp[h] = rec(l, m - 1, ul, ur, m) + rec(m + 1, r, ul, ur, m); if (p == 0) { return dp[h]; } if (p == l - 1) { int q = 0; //for (int i = ul + 1; i <= ur - 1; ++i) int s = upper_bound(all(v[m]), ul) - v[m].begin(); for (int ii = s; ii < sz(v[m]); ++ii) { int i = v[m][ii]; if (!(ul < i && i < ur)) break; bool z = false; if (b[i] == a[p]) { z = true; ++q; } if (i < m && m < ur && a[m] == b[m]) ++q; if (z) dp[h] = max(dp[h], q + rec(l, m - 1, i, ur, m) + rec(m + 1, r, i, ur, m)); if (i < m && m < ur && a[m] == b[m]) --q; } } else if (p == r + 1) { int q = 0; //for (int i = ur - 1; i >= ul + 1; --i) int s = lower_bound(all(v[m]), ur) - v[m].begin(); for (int ii = s - 1; ii >= 0; --ii) { int i = v[m][ii]; if (!(ul < i && i < ur)) continue; bool z = false; if (b[i] == a[p]) { z = true; ++q; } if (ul < m && m < i && a[m] == b[m]) ++q; dp[h] = max(dp[h], q + rec(l, m - 1, ul, i, m) + rec(m + 1, r, ul, i, m)); if (ul < m && m < i && a[m] == b[m]) --q; } } else assert(false); return dp[h]; } int solv0() { for (int l = 1; l <= n; ++l) { maxi[l][l] = l; for (int r = l + 1; r <= n; ++r) { maxi[l][r] = maxi[l][r - 1]; if (a[r] > a[maxi[l][r]]) maxi[l][r] = r; } } for (int i = 1; i <= n; ++i) v[i].clear(); rec0(1, n, 0); //dp.clear(); return rec(1, n, 0, n + 1, 0); } int p[N]; int ul[N], ur[N]; int solv2() { for (int i = 1; i <= n; ++i) { p[i] = p[i - 1]; if (a[i] == b[i]) ++p[i]; } ul[0] = 0; for (int i = 1; i <= n; ++i) { if (a[i] > b[i]) { ul[i] = i; } else { ul[i] = ul[i - 1]; } } ur[n + 1] = n + 1; for (int i = n; i >= 1; --i) { if (a[i] > b[i]) { ur[i] = i; } else { ur[i] = ur[i + 1]; } } int ans = 0; for (int i = 1; i <= n; ++i) { if (a[i] <= b[i]) { if (p[ur[i] - 1] - p[ul[i]] > 0) ++ans; } } return ans; } void solv() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> b[i]; if (n <= 5000) { cout << solv0() << "\n"; return; } bool z2 = true; for (int i = 1; i <= n; ++i) { if (b[i] != b[1]) { z2 = false; break; } } if (z2) { cout << solv2() << "\n"; return; } } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); /*int st = 100; while (st--) { n = rnf() % 100 + 1; for (int i = 1; i <= n; ++i) { a[i] = rnf() % 100 + 1; } b[1] = a[rnf() % n + 1]; for (int i = 2; i <= n; ++i) b[i] = b[1]; if (solv0() != solv2()) { cout << "WA\n"; return 0; } } cout << "OK\n"; return 0;*/ int tt = 1; //cin >> tt; while (tt--) { solv(); } return 0; }

Compilation message (stderr)

exam.cpp: In function 'int rec(int, int, int, int, int)':
exam.cpp:118:18: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  118 |             bool z = false;
      |                  ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...