| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 633900 | fadi57 | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB | 
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
const ll inf =1e18;
const ll mod=998244353;
ll findGap(int N, int T){
ll mn=0; ll mx=inf;
MinMax( 0,  inf, &mn,  &mx);
ll st=mn;ll en=mx;
ll len=(mx-(mn+1))/(n-1);
vector<pair<ll,ll>>v;
for(ll i=mn;<mx;i+=len){
      MinMax( i,  i+len-1, &mn,  &mx);
    if(mn!=-1){
        v.push_back({mn,mx});
    }
    
}
ans=len;
ans=max(ans,v[0].first-st);ans=max(ans,en-v[v.size().-1].second);
for(int i=1;i<v.size();i++){
    ans=max(ans,v[i].first-v[i-1].second);
}
return ans;
}
/*
int main()
{
   int t;//cin>>t;
   t=1;
   while(t--){
     ll n,m;cin>>n>>m;
     for(int i=1;i<=n;i++){
        cin>>a[i];
     }
     ll ans=0;
     for(int i=1;i<=n;i++){
        if(a[i]!=a[i+1]){
            ans+=(n-(i))*(i);
            same[i]=1;
        }else{
          same[i]=0;
        }
     }
     ans+=(((n)*(n+1))/2);
     while(m--){
        int x,y;
        cin>>x>>y;
        int ok=1;
        if(x<n){
            ans-=same[x]*(n-(x))*(x);
        }
        if(x>1){
            ans-=same[x-1]*(n-(x-1))*(x-1);
        }
            a[x]=y;
        if(x<n){
           same[x]=(a[x]!=a[x+1]);
        }
        if(x>1){
            same[x-1]=(a[x-1]!=a[x]);
        }
        if(x<n){
            ans+=same[x]*(n-(x))*(x);
        } if(x>1){
            ans+=same[x-1]*(n-(x-1))*(x-1);
        }
cout<<ans<<"\n";
     }
   //  cout<<ans<<"\n";
   }
}
*/
