Submission #1118033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118033		0pt1mus23	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	0 / 100	2076 ms	108880 KiB

plaukimo_varzybos

// Ali - OVERKILLL BABE 

// #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;

struct ups{
    vector<int> T;
    ups(int n){
        T.resize(n*4 +23,inf);
    }
    void upd(int node,int idx,int l,int r,int v){
        if(l==r){
            T[node]=v;
            return;
        }
        int mid = (l+r)/2;
        if(idx<=mid){
            upd(2*node,idx,l,mid,v);
        }
        else{
            upd(2*node +1,idx,mid+1,r,v);
        }
        T[node]=min(T[2*node],T[2*node +1]);
    }
    int qry(int node,int lx,int rx,int l,int r){
        if(lx>rx){
            return inf;
        }
        if(l>rx || r<lx){
            return inf;
        }
        if(l>=lx && r<=rx){
            return T[node];
        }
        int mid= (l+r)/2;

        return min(
            qry(2*node,lx,rx,l,mid),
            qry(2*node +1,lx,rx,mid+1,r)
        );
    }
};

struct upsmax{
    vector<int> T;
    upsmax(int n){
        T.resize(n*4 +23,-inf);
    }
    void upd(int node,int idx,int l,int r,int v){
        if(l==r){
            T[node]=v;
            return;
        }
        int mid = (l+r)/2;
        if(idx<=mid){
            upd(2*node,idx,l,mid,v);
        }
        else{
            upd(2*node +1,idx,mid+1,r,v);
        }
        T[node]=max(T[2*node],T[2*node +1]);
    }
    int qry(int node,int lx,int rx,int l,int r){
        if(lx>rx){
            return -inf;
        }
        if(l>rx || r<lx){
            return -inf;
        }
        // cout<<lx<<" "<<rx<<" "<<l<<" "<<r<<endl;
        if(l>=lx && r<=rx){
            return T[node];
        }
        int mid= (l+r)/2;
        return max(
            qry(2*node,lx,rx,l,mid),
            qry(2*node +1,lx,rx,mid+1,r)
        );
    }
};

void fast(){
    int n,a,b;
    cin>>n>>a>>b;   
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(all(arr));
    int lx=0;
    int rx =2e9;
    int ans=0;
    ups mins(n+23);
    upsmax maxs(n+23);
    for(int i=0;i<n;i++){
        mins.upd(1,i,0,n-1,arr[i]);
        maxs.upd(1,i,0,n-1,arr[i]);
    }
    // cout<<maxs.qry(1,0,3,0,n-1)<<endl;
    while(lx<=rx){
        ups dp(n+23);

        int mid = (lx+rx)/2;
        // cout<<lx<<" "<<rx<<" --- "<<mid<<endl;
        dp.upd(1, a-1, 0,n-1, maxs.qry(1,0,a-1,0,n-1) - mins.qry(1,0,a-1,0,n-1) );
        // cout<<maxs.qry(1,0,a-1,0,n-1) - mins.qry(1,0,a-1,0,n-1)<<endl;
        for(int i=a;i<n;i++){

            int r = max((int)0,i - a +1);
            int l = max((int)0,i-b +1);
            int z = inf;
            // cout<<mid<<" "<<l<<" "<<r<<" "<<i<<endl;
            // cout<<maxs.qry(1,l,i,0,n-1)- mins.qry(1,l,i,0,n-1)<<endl;
            while(l<=r){
                // cout<<mid<< " "<<l<<" "<<r<<endl;
                int m = (l+r)/2;
                if( maxs.qry(1,m,i,0,n-1) - mins.qry(1,m,i,0,n-1) <= mid ){
                    r = m-1;
                    z = m;
                }
                else{
                    l = m+1;
                }
            }
            // cout<<mid<<" "<<i<<" "<<z<<endl;
            if(z!=inf){
                int x = dp.qry(1,max((int)0,z-1),max((int)0,i-a),0,n-1);
                // cout<<i<<" => "<<x<<endl;
                dp.upd(1,i,0,n-1,x);
            }
        }
        // cout<<mid<<" ............ "<<dp.qry(1,n-1,n-1,0,n-1)<<endl;
        if(dp.qry(1,n-1,n-1,0,n-1) <= mid){
            rx = mid-1;
            ans = mid;
        }
        else{
            lx = 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