Submission #1294946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294946		Hamed_Ghaffari	Sparklers (JOI17_sparklers)	C++20	100 / 100	24 ms	2788 KiB

sparklers

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

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second
#define mid ((l+r)>>1)
#define lc id<<1
#define rc lc|1
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())
#define mins(a, b) (a = min(a, b))
#define maxs(a, b) (a = max(a, b))

const int MXN = 1e5+5;

using big = __int128_t;

int n, k;
ll t, x[MXN];
big y[MXN];


/*

x[r] - x[l] <= (r-l)*t*s*2
x[r] - r*t*s*2 <= x[l] - l*t*s*2

y[i] = x[i] - i*t*s2

y[r] <= y[l]

*/

bool check(ll s) {
    for(int i=1; i<=n; i++) y[i] = x[i] - (big)i*t*s*2;
    if(y[1]<y[n]) return 0;
    int L=k, R=k;
    for(int i=k-1; i>=1; i--)
        if(y[i]>=y[L]) L = i;
    for(int i=k+1; i<=n; i++)
        if(y[i]<=y[R]) R = i;
    int l=k, r=k;
    big mx=y[k], mn = y[k];
    while(L<l || r<R) 
        if(L<l && y[l-1]>=mn)
            maxs(mx, y[--l]);
        else if(r<R && mx>=y[r+1])
            mins(mn, y[++r]);
        else return 0;
    l=1, r=n;
    mx = y[1], mn = y[n];
    while(l<L || R<r) 
        if(l<L && y[l+1]>=mn)
            maxs(mx, y[++l]);
        else if(R<r && mx>=y[r-1])
            mins(mn, y[--r]);
        else return 0;
    return 1;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k >> t;
    for(int i=1; i<=n; i++) cin >> x[i];
    int l=0, r=x[n];
    while(r-l>1)
        (check(mid) ? r : l) = mid;
    cout << r << '\n';
    return 0;
}

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