Submission #1032634

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032634	2024-07-24T04:47:31 Z	caterpillow	Exam (eJOI20_exam)	C++17	65 / 100	81 ms	98564 KB

exam

#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

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

Subtask #1
14.0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	416 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4188 KB	Output is correct
2	Incorrect	4 ms	860 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	1272 KB	Output is correct
3	Correct	11 ms	16220 KB	Output is correct
4	Correct	62 ms	90908 KB	Output is correct
5	Correct	66 ms	98388 KB	Output is correct
6	Correct	74 ms	98384 KB	Output is correct

Subtask #4
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	856 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
16.0 / 16.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	416 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	604 KB	Output is correct
11	Correct	600 KB	Output is correct
12	Correct	604 KB	Output is correct
13	Correct	604 KB	Output is correct
14	Correct	604 KB	Output is correct

Subtask #6
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 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	416 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	1272 KB	Output is correct
9	Correct	11 ms	16220 KB	Output is correct
10	Correct	62 ms	90908 KB	Output is correct
11	Correct	66 ms	98388 KB	Output is correct
12	Correct	74 ms	98384 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	600 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	0 ms	604 KB	Output is correct
21	Correct	0 ms	604 KB	Output is correct
22	Correct	2 ms	4188 KB	Output is correct
23	Correct	81 ms	98356 KB	Output is correct
24	Correct	66 ms	98468 KB	Output is correct
25	Correct	50 ms	98564 KB	Output is correct
26	Correct	49 ms	98388 KB	Output is correct
27	Correct	50 ms	98388 KB	Output is correct
28	Correct	52 ms	98396 KB	Output is correct
29	Correct	63 ms	98388 KB	Output is correct
30	Correct	64 ms	98384 KB	Output is correct
31	Correct	64 ms	98384 KB	Output is correct
32	Correct	58 ms	98388 KB	Output is correct

Submission #1032634

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 0 / 12.0

Subtask #3 13.0 / 13.0

Subtask #4 0 / 23.0

Subtask #5 16.0 / 16.0

Subtask #6 22.0 / 22.0

Subtask #1
14.0 / 14.0

Subtask #2
0 / 12.0

Subtask #3
13.0 / 13.0

Subtask #4
0 / 23.0

Subtask #5
16.0 / 16.0

Subtask #6
22.0 / 22.0