Submission #1177309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177309		ASN49K	Sparklers (JOI17_sparklers)	C++20	100 / 100	32 ms	1864 KiB

sparklers

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
const int inf=1e9;
using i64 = long long;
const i64 INF=1e18;
#define int long long

const int N_MAX=100'000;
int a[N_MAX],n,k,t;

[[gnu::optimize("O3")]][[gnu::target("avx2")]] bool test(int s)
{

    std::vector<int>xx(n);
    for(int i=0;i<n;i++)
    {
        xx[i]=a[i]-2*s*t*i;
        ///std::cout<<xx[i]<<' ';
    }
    if(xx[0]<xx[n-1])
    {
        return false;
    }
    int l=k,r=k;
    bool modify=true;
    while(modify)
    {
        modify=false;

        int best_l=l;
        while(l>0 && xx[l-1]>=xx[r])
        {
            l--;
            if(xx[best_l]<=xx[l])
            {
                best_l=l;
                modify=true;
            }
        }
        l=best_l;

        int best_r=r;
        while(r+1<n && xx[r+1]<=xx[l])
        {
            r++;
            if(xx[best_r]>=xx[r])
            {
                best_r=r;
                modify=true;
            }
        }
        r=best_r;
    }
    //std::cout<<l<<' '<<r<<'\n';
    int save_l=l,save_r=r;

    l=0,r=n-1;
    modify=true;
    while(modify)
    {
        modify=false;
        int best_l=l;
        while(l<save_l && xx[l+1]>=xx[r])
        {
            l++;
            if(xx[best_l]<=xx[l])
            {
                best_l=l;
                modify=true;
            }
        }
        l=best_l;

        int best_r=r;
        while(r>save_r && xx[r-1]<=xx[l])
        {
            r--;
            if(xx[best_r]>=xx[r])
            {
                best_r=r;
                modify=true;
            }
        }
        r=best_r;
    }
    //std::cout<<l<<' '<<r<<'\n';
        //std::cout<<min[1][2]<<' '<<max[1][2]<<'\n';
    return l>=save_l && r<=save_r;
}
main()
{
    std::cin>>n>>k>>t;
    k--;

    for(int i=0;i<n;i++)
    {
        std::cin>>a[i];
    }
    //std::cout<<test(5);
    //return 0;

    int st=0,dr=a[n-1],rez=-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(test(mid))
        {
            dr=mid-1;
            rez=mid;
        }
        else
        {
            st=mid+1;
        }
    }
    assert(rez!=-1);

    std::cout<<rez;
    return 0;
}
//0 100 100
//0 40 -20
/*
2 1 10
200
300
*/

Compilation message (stderr)

sparklers.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main()
      | ^~~~

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