Submission #200663

#	Time	Username	Problem	Language	Result	Execution time	Memory
200663		gs18115	Sparklers (JOI17_sparklers)	C++14	100 / 100	40 ms	2936 KiB

sparklers

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int n,k;
ll x[100010];
inline bool able(ll sp)
{
    vector<ll>v(n);
    for(int i=0;i<n;i++)
        v[i]=x[i]-sp*i*2;
    int l=k,r=k;
    ll lm=v[l],rm=v[r];
    for(int i=0;i<n;i++)
    {
        while(l>0&&v[l-1]>=rm)
            lm=max(lm,v[--l]);
        while(r<n-1&&v[r+1]<=lm)
            rm=min(rm,v[++r]);
    }
    if(r-l<n-1)
        return 0;
    lm=v[l=0];
    rm=v[r=n-1];
    if(lm<rm)
        return 0;
    for(int i=0;i<n;i++)
    {
        while(l<k&&v[l+1]>=rm)
            lm=max(lm,v[++l]);
        while(r>k&&v[r-1]<=lm)
            rm=min(rm,v[--r]);
    }
    return l==r;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t;
    cin>>n>>k>>t;
    k--;
    for(int i=0;i<n;i++)
        cin>>x[i];
    ll s=0;
    ll e=inf;
    while(s<e)
    {
        ll m=s+e>>1;
        if(able(m))
            e=m;
        else
            s=m+1;
    }
    cout<<(s+t-1)/t<<endl;
    return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll m=s+e>>1;
              ~^~

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