Submission #1118794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118794		0pt1mus23	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	0 / 100	2099 ms	26688 KiB

plaukimo_varzybos

// Ali

// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1e6+23, inf = 2e9, LG = 19,pr = 31;

void fast(){
    int n,a,b;
    cin>>n>>a>>b;
    assert(b<=n);
    int ans=-1;
    vector<int> arr(n);
    for(int i =0;i<n;i++){
        cin>>arr[i];
    }

    sort(all(arr));
    auto diff = [&](int x,int y,int m) -> int {
        return ((arr[y]-arr[x]) <= m) ;
    };

    int l=0;
    int r = inf;
    while(l<=r){
        int mid = (l+r)>>1;
        set<int> olar;
        if(diff(a-1,0,mid)){
            olar.ins(a-1);
        }
        for(int i=a;i<n;i++){
            if( (i+1)>=a && (i+1)<=b && diff(0,i,mid)){
                olar.ins(i);
            }
            else{
                int lx = max((int)0,i-b +1);
                int rx = i-a+1;
                int bb = -1;
                while(lx<=rx){
                    int mm = (lx+rx)>>1;
                    if(diff(mm,i,mid)){
                        rx = mm-1;
                        bb = mm;
                    }
                    else{
                        lx = mm+1;
                    }
                }
                if(bb!=-1){
                    lx = max((int)0,bb-1);
                    rx = i-a;
                    if(!olar.empty()){
                        auto it = olar.lower_bound(lx);
                        if( it!=olar.end() && *it <= rx){
                            olar.ins(i);
                        }
                    }
                }
            }
        }
        if(!olar.empty() && *olar.rbegin()==n-1){
            r = mid-1;
            ans=mid;
        }
        else{
            l = mid+1;
        }

    }

    putr(ans);
}

 
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40