Submission #546709

#	Time	Username	Problem	Language	Result	Execution time	Memory
546709		radal	Sparklers (JOI17_sparklers)	C++17	100 / 100	36 ms	3244 KiB

sparklers

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 3e5+20,mod = 998244353 ,inf = 2e9+10,maxm = (1 << 10)+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z;
}
ll tt;
int n,k,x[N];
ll a[N][2],sum;
pll val(bool f,ll t){
    int l = k,r = k;
    ll cur = t,sum1 = 0,sum2 = 0;
    if (f){
        cur = sum;
    }
    int po1 = l-1,po2 = r+1;
    while (1){
        bool fl = 0; 
        while (po1 >= 0 && sum1 <= 0 && sum1-t*f >= -cur){
            if (!f && sum1 -x[po1+1]+x[po1] < -cur) break;
       //     if (f && sum1 -x[k-po1]+x[k-1-po1] < -cur) break;
            sum1 += a[po1][f];
            po1--;
            fl = 1;
        }
        while (po2 < n && sum2 <= 0 && sum2-f*t >= -cur){
            if (!f && sum2 - x[po2]+x[po2-1] < -cur) break;
     //       if (f && sum2 -x[k-po2]+x[k-po2-1] < -cur) break;
            sum2 += a[po2][f];
            po2++;
            fl = 1;
        }
        if (sum1 >= 0){
            l = po1+1;
            cur += sum1;
            sum1 = 0;
        }
        if (sum2 >= 0){
            r = po2-1;
            cur += sum2;
            sum2 = 0;
        }
        if (!fl) break;
    }
    return {l,r};
}
inline bool check(ll t){
    sum = t;
    rep(i,k+1,n){
        a[i][0] = t-x[i]+x[i-1];
        sum += a[i][0];
    }
    rep(i,0,k){
        a[i][0] = t-x[i+1]+x[i];
        sum += a[i][0];
    }
    if (sum < 0) return 0;
    rep(i,0,k)
        a[i][1] = -a[k-i-1][0];
    rep(i,k+1,n)
        a[i][1] = -a[n-i+k][0];
    pll p1 = val(1,t),p0 = val(0,t);
  //  debug(p0.X);
    //debug(p1.X);
    if (k-p0.X+k-p1.X < k) return 0;
    if (p0.Y-k+p1.Y-k < n-k-1) return 0;
    return 1;
}
inline int bs(){
    int l = -1,r = inf,m;
    while (r-l > 1){
        m = (l+r) >> 1;
        if (check(2*m*tt)) r = m;
        else l = m;
    }
    return r;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> tt;
    k--;
    rep(i,0,n) cin >> x[i];
    cout << bs();
}

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