Submission #583803

#	Time	Username	Problem	Language	Result	Execution time	Memory
583803		79brue	Sparklers (JOI17_sparklers)	C++17	100 / 100	92 ms	7884 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
ll s;
ll arr[100002];

bool able(vector<ll> &v1, vector<ll> &v2){
    vector<pair<ll, ll> > vp1, vp2;
    ll prvMin = v1[0], tmpMax = v1[0];
    for(ll x: v1){
        tmpMax = max(tmpMax, x);
        if(x < prvMin){
            vp1.push_back(make_pair(tmpMax, x));
            prvMin = tmpMax = x;
        }
    }
    ll prvMax = v2[0], tmpMin = v2[0];
    for(ll x: v2){
        tmpMin = min(tmpMin, x);
        if(x > prvMax){
            vp2.push_back(make_pair(tmpMin, x));
            prvMax = tmpMin = x;
        }
    }
    reverse(vp1.begin(), vp1.end());
    reverse(vp2.begin(), vp2.end());
    ll L = v1[0], R = v2[0];
    while(!vp1.empty() || !vp2.empty()){
        if(!vp1.empty() && vp1.back().first <= R){
            L = vp1.back().second;
            vp1.pop_back();
        }
        else if(!vp2.empty() && vp2.back().first >= L){
            R = vp2.back().second;
            vp2.pop_back();
        }
        else return false;
    }
    return true;
}

bool able(ll speed){
    speed = min(speed * s * 2, ll(1e9));
    vector<ll> vecL, vecR;
    for(int i=k; i>=1; i--){
        vecL.push_back(speed * i - arr[i]);
    }
    for(int i=k; i<=n; i++){
        vecR.push_back(speed * i - arr[i]);
    }
    if(*max_element(vecL.begin(), vecL.end()) > *max_element(vecR.begin(), vecR.end())) return false;
    if(*min_element(vecL.begin(), vecL.end()) > *min_element(vecL.begin(), vecL.end())) return false;
    if(vecL.back() > vecR.back()) return false;

    auto it1 = min_element(vecL.begin(), vecL.end());
    auto it2 = max_element(vecR.begin(), vecR.end());
    vector<ll> vecL1(vecL.begin(), it1+1), vecL2(it1, vecL.end());
    vector<ll> vecR1(vecR.begin(), it2+1), vecR2(it2, vecR.end());
    reverse(vecL2.begin(), vecL2.end());
    reverse(vecR2.begin(), vecR2.end());

    if(!able(vecL1, vecR1)) return false;
    if(!able(vecL2, vecR2)) return false;
    return true;
}

int main(){
    scanf("%d %d %lld", &n, &k, &s);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    if(arr[1] == arr[n]){
        puts("0");
        return 0;
    }
    ll MIN = 1, MAX = 1e9, ANS = 1e9;
    while(MIN <= MAX){
        ll MID = (MIN + MAX) / 2;
        if(able(MID)) ANS = MID, MAX = MID-1;
        else MIN = MID+1;
    }
    printf("%lld", ANS);
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %d %lld", &n, &k, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:73:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

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