Submission #1182106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182106		Cyanmond	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	437 ms	7640 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<ll> s(n), f(m);
    for (auto &e : s) {
        cin >> e;
    }
    for (auto &e : f) {
        cin >> e;
    }
    if (n == 1) {
        auto mn = *min_element(f.begin(), f.end());
        auto mx = *max_element(f.begin(), f.end());
        if (mn < s[0] and s[0] < mx) {
            cout << -1 << endl;
            return;
        }
    }

    auto sol = [&](ll k, bool retrieve = false) {
        vector<int> dp(n + 1, 0);
        vector<vector<int>> del_list(n + 1);
        set<int> se;

        vector<int> prv(n + 1, -1);
        auto update = [&](int i, int pos, int p) {
            if (dp[i] < pos) {
                dp[i] = pos;
                prv[i] = p;
            }
        };

        for (int i = 0; i < n; ++i) {
            for (auto e : del_list[i]) {
                se.erase(e);
            }

            if (not se.empty()) {
                int pos = upper_bound(f.begin(), f.end(), s[i - 1] + k) - f.begin();
                update(i + 1, pos, *se.begin());
            }

            auto j = dp[i];
            if (j == m) {
                update(i + 1, m, i);
                continue;
            }
            if (s[i] <= f[j]) {
                int pos = upper_bound(f.begin(), f.end(), s[i] + k) - f.begin();
                update(i + 1, pos, i);
            } else {
                int pos = upper_bound(s.begin(), s.end(), f[j] + k) - s.begin();
                if (i < pos) {
                    se.insert(i);
                    del_list[pos].push_back(i);
                }
                if (f[j] + k >= s[i]) {
                    int pos = upper_bound(f.begin(), f.end(), s[i]) - f.begin();
                    update(i + 1, pos, -1);
                }
            }
        }

        if (not retrieve) {
            return dp;
        }

        vector<int> res(n);
        int cur = n;
        while (cur != 0) {
            int p = prv[cur];
            cerr << cur << ' ' << p << endl;
            if (p == -1) {
                p = cur - 1;
                res[p] = -1;
            } else if (p == cur - 1) {
                res[p] = 1;
            } else {
                for (int i = p; i < cur - 1; ++i) {
                    res[p] = 1;
                }
                res[cur - 1] = -1;
            }
            cur = p;
        }
        return res;
    };

    ll ok = 1ll << 30, ng = -1;
    while (ok - ng > 1) {
        auto md = (ok + ng) / 2;
        auto res = sol(md);
        if (res[n] == m) {
            ok = md;
        } else {
            ng = md;
        }
    }

    cout << ok << endl;
    auto res = sol(ok, true);
    for (auto e : res) {
        cout << (e == -1 ? 'L' : 'R');
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 27 / 27
• Subtask 5: 47 / 47