Submission #1198293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198293		og_matveychick1	Sparklers (JOI17_sparklers)	C++20	100 / 100	66 ms	6628 KiB

sparklers

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll N = 1e5 + 5;

ll n, k, t, a[N], b[N];

bool check(vector<pll> l, vector<pll> r) {
    ll il = 0, ir = 0;
    while (il != l.size() - 1 || ir != r.size() - 1) {
        if (il != l.size() - 1 && r[ir].first <= l[il + 1].second) il++;
        else if (ir != r.size() - 1 && l[il].first >= r[ir + 1].second) ir++;
        else return 0;
    }
    return 1;
}

bool check(ll s) {
    if (s * t > 1e9) return 1;
    for (ll i = 0; i < n; i++) b[i] = a[i] - 2 * s * t * i;
    vector<pll> L1, L2, R1, R2;
    L1 = {{b[k], b[k]}}, R1 = L1;
    L2 = {{b[0], b[0]}}, R2 = {{b[n - 1], b[n - 1]}};
    ll gl = max_element(b, b + k + 1) - b, gr = min_element(b + k, b + n) - b, f, x;
    x = b[k];
    f = 1e18;
    for (ll i = k - 1; i >= gl; i--) {
        f = min(f, b[i]);
        if (b[i] >= x) L1.push_back({b[i], f}), f = 1e18, x = b[i];
    }
    x = b[k];
    f = -1e18;
    for (ll i = k + 1; i <= gr; i++) {
        f = max(f, b[i]);
        if (b[i] <= x) R1.push_back({b[i], f}), f = -1e18, x = b[i];
    }
    x = b[0];
    f = 1e18;
    for (ll i = 0; i <= gl; i++) {
        f = min(f, b[i]);
        if (b[i] >= x) L2.push_back({b[i], f}), f = 1e18, x = b[i];
    }
    x = b[n - 1];
    f = -1e18;
    for (ll i = n - 1; i >= gr; i--) {
        f = max(f, b[i]);
        if (b[i] <= x) R2.push_back({b[i], f}), f = -1e18, x = b[i];
    }
    return check(L1, R1) & check(L2, R2);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k >> t, k--;
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll l = -1, r = 1e9 / t + 5;
    check(2);
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        (check(m) ? r : l) = m;
    }
    cout << r;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50