NOIP模拟赛T4 = LOJ2392 求条

[雷佳勉]

WA在了第二个样例但是由于这样例太大了条不了。

注意与LOJ2392有一点不同：本题坐标互不重复且不保证有序。

题解：

代码：

#include <bits/stdc++.h>
using namespace std;

#define int __int128
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define gn(u, v) for (int v : G.G[u])
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tomin(x, y) ((x) = min((x), (y)))
#define tomax(x, y) ((x) = max((x), (y)))
#define ck(mask, i) (((mask) >> (i)) & 1)
#define pq priority_queue
#define FLG (cerr << "Alive!" << endl);

constexpr int MAXN = 6e5 + 5;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;
long long n, k, t;
long long x[MAXN];
int lst[MAXN], rst[MAXN], ltp, rtp, lsum, rsum;
pair<int, int> l[MAXN], r[MAXN];
int lt, rt;

bool check(int v) {
    // cerr << v << endl;
    t *= 2 * v;
    ltp = rtp = lt = rt = lsum = rsum = 0;
    rep(i, 1, k - 1) {
        lst[++ltp] = x[i + 1] - x[i];
    }
    per(i, n, k + 1) {
        rst[++rtp] = x[i] - x[i - 1];
    }

    int ans = 0;

    while (ltp) {
        // cerr << ltp << endl;
        int i = ltp;
        int sum = 0, mn = 0;
        while (i) {
            sum -= lst[i] - t;
            tomin(mn, sum);
            i--;
            if (sum >= 0) {
                l[++lt] = mp(sum, mn);
                break;
            }
        }
        if (sum < 0) {
            lsum = -sum;
            break;
        } else {
            ltp = i;
        }
    }
    // FLG

    while (rtp) {
        // cerr << rtp << endl;
        int i = rtp;
        int sum = 0, mn = 0;
        while (i) {
            sum -= rst[i] - t;
            tomin(mn, sum);
            i--;
            if (sum >= 0) {
                r[++rt] = mp(sum, mn);
                break;
            }
        }
        if (sum < 0) {
            rsum = -sum;
            break;
        } else {
            rtp = i;
        }
    }


    int a = t;
    while (lt || rt) {
        // cerr << a << " " << l[lt].se << " " << r[rt].se << " " << lt << " " << rt << endl;
        if ((!lt || a + l[lt].se < 0) && (!rt || a + r[rt].se < 0)) {
            t /= 2 * v;
            return false;
        }
        if (lt && a + l[lt].se >= 0) {
            a += l[lt].fi;
            lt--;
        }
        if (rt && a + r[rt].se >= 0) {
            a += r[rt].fi;
            rt--;
        }
    }
    // cerr << lsum << " " << rsum << endl;


    lt = rt = 0;
    int e = a - lsum - rsum;
    // cerr << e << " " << lsum << " " << rsum << endl;

    reverse(lst + 1, lst + ltp + 1);
    reverse(rst + 1, rst + rtp + 1);
    
    while (ltp) {
        int i = ltp;
        int sum = 0, mn = 0;
        while (i) {
            sum += lst[i] - t;
            tomin(mn, -sum);
            i--;
            if (sum >= 0) {
                l[++lt] = mp(sum, mn);
                break;
            }
        }
        if (sum < 0) {
            lsum = -sum;
            break;
        } else {
            ltp = i;
        }
    }

    while (rtp) {
        int i = rtp;
        int sum = 0, mn = 0;
        while (i) {
            sum += rst[i] - t;
            tomin(mn, -sum);
            i--;
            if (sum >= 0) {
                r[++rt] = mp(sum, mn);
                break;
            }
        }
        if (sum < 0) {
            rsum = -sum;
            break;
        } else {
            rtp = i;
        }
    }

    while (lt || rt) {
        // cerr << e << " " << l[lt].se << " " << r[rt].se << " " << lt << " " << rt << endl;
        if ((!lt || e + l[lt].se < 0) && (!rt || e + r[rt].se < 0)) {
            t /= 2 * v;
            return false;
        }
        if (lt && e + l[lt].se >= 0) {
            e += l[lt].fi;
            lt--;
        }
        if (rt && e + r[rt].se >= 0) {
            e += r[rt].fi;
            rt--;
        }
    }
    t /= 2 * v;

    return true;
}

long long bin() {
    int ans = 0;
    for (int i = (1 << 30); i; i >>= 1) {
        if (!check(i + ans))
            ans += i;
    }
    return ans + 1;
}

signed main() {
#ifdef ONLINE_JUDGE
    freopen("virus.in", "r", stdin);
    freopen("virus.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k >> t;
    rep(i, 1, n) {
        cin >> x[i];
    }
    k = x[k];
    sort(x + 1, x + n + 1);
    k = lower_bound(x + 1, x + n + 1, k) - x;

    // cerr << check(0);

    // cerr << check(8) << endl;

    // cerr << check(4) << endl;

    cout << bin() << endl;

    return 0;
}