Submission #1032634

#TimeUsernameProblemLanguageResultExecution timeMemory
1032634caterpillowExam (eJOI20_exam)C++17
65 / 100
81 ms98564 KiB
#include <bits/stdc++.h> using namespace std; using db = long double; using ll = long long; using pl = pair<ll, ll>; using pi = pair<int, int>; #define vt vector #define f first #define s second #define pb push_back #define all(x) x.begin(), x.end() #define size(x) ((int) (x).size()) #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define F0R(i, b) FOR (i, 0, b) #define endl '\n' const ll INF = 1e18; const int inf = 1e9; template<typename... Args> // tuples ostream& operator<<(ostream& os, tuple<Args...> t) { apply([&](Args... args) { string dlm = "{"; ((os << dlm << args, dlm = ", "), ...); }, t); return os << "}"; } template<typename T, typename V> // pairs ostream& operator<<(ostream& os, pair<T, V> p) { return os << "{" << p.f << ", " << p.s << "}"; } template<class T, class = decltype(begin(declval<T>()))> // iterables typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& os, const T& v) { string dlm = "{"; for (auto& i : v) os << dlm << i, dlm = ", "; return os << "}"; } template <typename T, typename... V> void printer(string pfx, const char *names, T&& head, V&& ...tail) { int i = 0; while (names[i] && names[i] != ',') i++; constexpr bool is_str = is_same_v<decay_t<T>, const char*>; if (is_str) cerr << " " << head; else cerr << pfx, cerr.write(names, i) << " = " << head; if constexpr (sizeof...(tail)) printer(is_str ? "" : ",", names + i + 1, tail...); else cerr << endl; } #ifdef LOCAL #define dbg(...) printer(to_string(__LINE__) + ": ", #__VA_ARGS__, __VA_ARGS__) #else #define dbg(x...) #define cerr if (0) std::cerr #endif tuple<int, vt<int>, vt<int>> read() { int n; cin >> n; vt<int> a(n), b(n), c; F0R (i, n) cin >> a[i], c.pb(a[i]); F0R (i, n) cin >> b[i], c.pb(b[i]); sort(all(c)); c.erase(unique(all(c)), c.end()); auto ord = [&] (int x) { return lower_bound(all(c), x) - c.begin(); }; for (auto& x : a) x = ord(x); for (auto& x : b) x = ord(x); return {n, a, b}; } /* we need to figure out what final configurations of A are possible a person's level can only increase rules: 1. some dude's work will always be a continuous range 2. some dude's work can only spread up to the next larger guy on either side 3. left to right ordering must be the same as long as final state assignments follow these, its possible to construct subtask 2: B is equal bruh subtask 4: elements of A are distinct if kid i was to pass, then we know who gave him their work let dp[i][j] be the max passes, only allowing the first i kids to spread their work, considering only the first j kids in the line everything else: n <= 5000 let dp[i][j] be the max value of assigning some work to the first j kids, using only the first i kids' work for each kid, they are allowed to "spread" their range up to the next larger element on either side for each prefix, starting from the first kid he can claim, find the new max value of the prefix, additionally allowing the kid to claim some suffix of it */ int n; vt<int> a, b; struct SegTree { int n; vt<int> seg; void init(int _n) { for (n = 1; n < _n; n *= 2); seg.resize(2 * n); } void chmax(int l, int r, int v) { dbg(l, r, v); for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) seg[l] = max(seg[l], v), l++; if (r & 1) r--, seg[r] = max(seg[r], v); } } int operator[](int i) { int res = seg[i += n]; while (i /= 2) res = max(res, seg[i]); return res; } }; void solve3() { vt<int> rnum(2 * n, -1); F0R (i, n) rnum[a[i]] = i; vt<pi> rng(n); vt<int> stk; F0R (i, n + 1) { while (size(stk) && (i == n || a[stk.back()] < a[i])) { rng[stk.back()].s = i; stk.pop_back(); } stk.pb(i); } stk.clear(); ROF (i, -1, n) { while (size(stk) && (i == -1 || a[stk.back()] < a[i])) { rng[stk.back()].f = i; stk.pop_back(); } stk.pb(i); } vt<vt<int>> nums(2 * n); F0R (i, n) { int j = rnum[b[i]]; if (j == -1) continue; if (rng[j].f <= i && i <= rng[j].s) { nums[b[i]].pb(i); } } SegTree dp; dp.init(n + 1); dbg(a); dbg(b); dbg(rnum); F0R (i, n) { if (rnum[b[i]] == -1) continue; int m = size(nums[a[i]]); dbg(m, nums[a[i]]); FOR (j, 0, m) { dp.chmax(nums[a[i]][j] + 1, n, dp[nums[a[i]][j]] + 1); } } cout << dp[n] << endl; } void solve2() { vt<pi> rng(n); vt<int> stk; F0R (i, n + 1) { while (size(stk) && (i == n || a[stk.back()] < a[i])) { rng[stk.back()].s = i; stk.pop_back(); } stk.pb(i); } stk.clear(); ROF (i, -1, n) { while (size(stk) && (i == -1 || a[stk.back()] < a[i])) { rng[stk.back()].f = i; stk.pop_back(); } stk.pb(i); } vt<pi> todo; F0R (i, n) { if (a[i] == b[0]) { todo.pb(rng[i]); } } sort(all(todo)); int ans = 0; int l = 0, r = 0; for (auto [lo, hi] : todo) { hi++; if (lo <= r) { r = max(r, hi); } else { ans += r - l; tie(l, r) = {lo, hi}; } } cout << ans + r - l << endl; } void solve1() { vt<vt<int>> dp(n + 1, vt<int>(n + 1)); // 1-indexed vt<pi> rng(n); // reachable range F0R (i, n) { int j = i; while (j < n && a[j] <= a[i]) j++; rng[i].s = j - 1; j = i; while (j >= 0 && a[j] <= a[i]) j--; rng[i].f = j + 1; } dbg(rng); // dp F0R (i, n) { dbg(dp[i]); F0R (j, n + 1) dp[i + 1][j] = dp[i][j]; auto [l, r] = rng[i]; int best = dp[i][l]; FOR (j, l, r + 1) { best = max(best + (b[j] == a[i]), dp[i][j + 1]); dp[i + 1][j + 1] = best; } } cout << dp[n][n] << endl; } main() { cin.tie(0)->sync_with_stdio(0); tie(n, a, b) = read(); if (n <= 5000) { solve1(); } else { int v = b[0]; bool is_same = true; FOR (i, 1, n) is_same &= (b[i] == v); if (is_same) solve2(); else solve3(); } }

Compilation message (stderr)

exam.cpp:233:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  233 | main() {
      | ^~~~
#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...