Submission #464948

#TimeUsernameProblemLanguageResultExecution timeMemory
464948SamAndExam (eJOI20_exam)C++17
37 / 100
134 ms8336 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 M = 25000007; bool isprime(int x) { if (x <= 1) return false; for (int i = 2; i * i <= x; ++i) { if (x % i == 0) return false; } return true; } int n; int a[N], b[N]; int ul[N], ur[N]; void pre() { stack<int> s; for (int i = 1; i <= n; ++i) { while (!s.empty() && a[s.top()] <= a[i]) s.pop(); if (s.empty()) ul[i] = 0; else ul[i] = s.top(); s.push(i); } while (!s.empty()) s.pop(); for (int i = n; i >= 1; --i) { while (!s.empty() && a[s.top()] <= a[i]) s.pop(); if (s.empty()) ur[i] = n + 1; else ur[i] = s.top(); s.push(i); } } int dp[N0][N0]; int solv6() { int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (a[i] == b[j] && ul[i] < j && j < ur[j]) { dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1); } dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]); dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); } } for (int i = 1; i <= n + 1; ++i) for (int j = 1; j <= n + 1; ++j) ans = max(ans, dp[i][j]); return ans; } int p[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; } map<int, int> mp; int maxu[N * 4]; void ubd(int tl, int tr, int x, int y, int pos) { if (tl == tr) { maxu[pos] = y; return; } int m = (tl + tr) / 2; if (x <= m) ubd(tl, m, x, y, pos * 2); else ubd(m + 1, tr, x, y, pos * 2 + 1); maxu[pos] = max(maxu[pos * 2], maxu[pos * 2 + 1]); } int qry(int tl, int tr, int l, int r, int pos) { if (l > r) return 0; if (tl == l && tr == r) return maxu[pos]; int m = (tl + tr) / 2; return max(qry(tl, m, l, min(m, r), pos * 2), qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1)); } int solv4() { for (int i = 1; i <= n; ++i) mp[a[i]] = i; for (int i = 1; i <= n; ++i) { if (mp.find(b[i]) == mp.end()) continue; int x = mp[b[i]]; if (ul[x] < i && i < ur[x]) { ubd(1, n, x, qry(1, n, 1, x, 1) + 1, 1); } } return maxu[1]; } void solv() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> b[i]; bool z2 = true; for (int i = 1; i <= n; ++i) { if (b[i] != b[1]) { z2 = false; break; } } if (z2) { cout << solv6() << "\n"; return; } pre(); if (n <= 5000) { cout << solv6() << "\n"; return; } cout << solv4() << "\n"; } 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); while (!isprime(M)) ++M; /*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; }
#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...