oj.uz

Submission #1032636

# Submission time Handle Problem Language Result Execution time Memory
1032636 2024-07-24T04:51:05 Z caterpillow Exam (eJOI20_exam) C++17
100 / 100
 92 ms 98600 KB 
#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 - 1;
            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 + 1;
            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 - 1;
            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 + 1;
            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) {
        dbg(lo, hi);
        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

exam.cpp:234:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  234 | main() {
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 6 ms 856 KB Output is correct
3 Correct 19 ms 3700 KB Output is correct
4 Correct 12 ms 3304 KB Output is correct
5 Correct 35 ms 4812 KB Output is correct
6 Correct 15 ms 3256 KB Output is correct
7 Correct 17 ms 3284 KB Output is correct
8 Correct 36 ms 4560 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 11 ms 16216 KB Output is correct
4 Correct 67 ms 90732 KB Output is correct
5 Correct 69 ms 98396 KB Output is correct
6 Correct 85 ms 98348 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 20 ms 4452 KB Output is correct
3 Correct 48 ms 9648 KB Output is correct
4 Correct 56 ms 10412 KB Output is correct
5 Correct 57 ms 12308 KB Output is correct
6 Correct 55 ms 11436 KB Output is correct
7 Correct 52 ms 11692 KB Output is correct
8 Correct 45 ms 9692 KB Output is correct
9 Correct 55 ms 11228 KB Output is correct
10 Correct 51 ms 11540 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 11 ms 16216 KB Output is correct
10 Correct 67 ms 90732 KB Output is correct
11 Correct 69 ms 98396 KB Output is correct
12 Correct 85 ms 98348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 604 KB Output is correct
22 Correct 2 ms 4204 KB Output is correct
23 Correct 92 ms 98560 KB Output is correct
24 Correct 65 ms 98376 KB Output is correct
25 Correct 57 ms 98384 KB Output is correct
26 Correct 68 ms 98384 KB Output is correct
27 Correct 55 ms 98384 KB Output is correct
28 Correct 53 ms 98384 KB Output is correct
29 Correct 67 ms 98600 KB Output is correct
30 Correct 73 ms 98592 KB Output is correct
31 Correct 74 ms 98592 KB Output is correct
32 Correct 61 ms 98376 KB Output is correct