Submission #1309954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309954		kikitop1gg	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	52 ms	14656 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf 1000000000000000000
#define all(x) (x).begin(), (x).end()

ll n, m;
vi a, b;
mi sprink;
vi pref;
ll mxPos;
vi comp2;

ll dist(ll x, ll y) {
    return comp2[x] - comp2[y];
}

string solve(ll k) {
    if(n == 1) {
        if(b[0] < a[0] && b.back() > a[0]) {
            return "";
        }
        ll need = max(abs(dist(b[0], a[0])), abs(dist(b.back(), a[0])));
        if(need > k) return "";
        if(b[0] < a[0]) return "L";
        return "R";
    }

    if(dist(a[0], b[0]) > k) return "";
    vvi dp(n, vi(2, -inf));
    vvi prv(n, vi(2, -1));
    dp[0][0] = pref[a[0]];
    if(pref[a[0]] == 0) {
        ll last = upper_bound(all(comp2), comp2[a[0]] + k) - comp2.begin() - 1;
        dp[0][1] = pref[last + 1];
    }
    else dp[0][1] = 0;

    for(int i = 1; i < n; i++) {
        ll x = a[i], y = a[i - 1];
        for(int j = 0; j < 2; j++) {
            for(int prev = 0; prev < 2; prev++) {
                if(dp[i - 1][prev] == -inf) continue;
                ll last = dp[i - 1][prev];
                if(last == m) {
                    dp[i][j] = m;
                    prv[i][j] = prev;
                    continue;
                }
                ll firstFlower = a[last];
                if(j == 0) {
                    if(dist(x, firstFlower) > k) continue;
                    if(prev == 0) {
                        ll newVal = pref[x];
                        if(newVal > dp[i][j]) {
                            dp[i][j] = newVal;
                            prv[i][j] = prev;
                        }
                    }
                    else {
                        ll end = upper_bound(all(comp2), comp2[y] + k) - comp2.begin();
                        ll newVal = max(pref[x], pref[end]);
                        if(newVal > dp[i][j]) {
                            dp[i][j] = newVal;
                            prv[i][j] = prev;
                        }
                    }
                }
                else {
                    if(prev == 0) {
                        if(firstFlower < x) {
                            if(last > dp[i][j]) {
                                dp[i][j] = last;
                                prv[i][j] = prev;
                            }
                        }
                        else {
                            ll end = upper_bound(all(comp2), comp2[x] + k) - comp2.begin();
                            if(pref[end] > dp[i][j]) {
                                dp[i][j] = pref[end];
                                prv[i][j] = prev;
                            }
                        }
                    }
                    else {
                        if(firstFlower < y) continue;
                        if(firstFlower < x) {
                            dp[i][j] = max(dp[i][j], last);
                            if(last > dp[i][j]) {
                                dp[i][j] = last;
                                prv[i][j] = prev;
                            }
                        }
                        else {
                            ll end = upper_bound(all(comp2), comp2[x] + k) - comp2.begin();
                            dp[i][j] = max(dp[i][j], pref[end]);
                            if(pref[end] > dp[i][j]) {
                                dp[i][j] = pref[end];
                                prv[i][j] = prev;
                            }
                        }
                    }
                }
            }
        }
    }

    ll from = -1;
    for(int i = 0; i < 2; i++) {
        if(dp[n - 1][i] == m) {
            from = i;
        }
    }
    if(from == -1) return "";
    
    ll i = n - 1;
    string ans;
    while(from != -1) {
        if(from == 0) ans += "L";
        else ans += "R";

        from = prv[i][from];
        i--;
    }

    reverse(all(ans));
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    a = vi(n), b = vi(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    if(m == 0) {
        cout << "0\n";
        return 0;
    }
    if(n == 0) {
        cout << "-1\n";
        return 0;
    }

    si vals;
    for(auto x : a) vals.insert(x);
    for(auto x : b) vals.insert(x);
    mi comp;
    for(auto x : vals) {
        comp[x] = comp.size();
        comp2.push_back(x);
    }
    for(int i = 0; i < n; i++) a[i] = comp[a[i]];
    for(int i = 0; i < m; i++) b[i] = comp[b[i]];

    for(auto x : a) {
        sprink[x]++;
    }
    vi newB;
    for(int i = 0; i < m; i++) {
        if(sprink.count(b[i])) continue;
        if(newB.size() > 0 && newB.back() == b[i]) continue;
        newB.push_back(b[i]);
    }
    b = newB;
    m = b.size();
    if(m == 0) {
        cout << "0\n";
        return 0;
    }
    mxPos = vals.size();
    pref = vi(mxPos + 1, 0);
    ll ind = 0;
    for(int i = 0; i < mxPos; i++) {
        pref[i + 1] = pref[i];
        while(ind < m && b[ind] == i) {
            pref[i + 1]++;
            ind++;
        }
    }
    
    ll ans = -1;
    string s;
    ll l = 0, r = INT_MAX;
    while(l <= r) {
        ll d = (l + r) / 2;
        string cur = solve(d);
        if(cur != "") {
            ans = d;
            s = cur;
            r = d - 1;
        }
        else l = d + 1;
    }
    cout << ans << '\n';
    if(ans != -1) cout << s << '\n';
    return 0;
}

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