Submission #219557

#	Time	Username	Problem	Language	Result	Execution time	Memory
219557		quocnguyen1012	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	100 / 100	564 ms	13048 KiB

plaukimo_varzybos

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int N, a[maxn], l, r;

bool check(int diff)
{
  //cerr << diff << '\n';
  int i = 1;
  deque<int> gr;
  gr.pb(0);
  while(i <= N && gr.size()){
    if(i - gr.front() >= l){
      if(i - gr.front() <= r && a[i] - a[gr.front() + 1] <= diff)
        gr.pb(i), ++i;
      else gr.pop_front();
    }
    else ++i;
  }
  return (gr.size() && gr.back() == N);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> l >> r;
  for(int i = 1; i <= N; ++i)
    cin >> a[i];
  sort(a + 1, a + 1 + N);
  int lo = 0, hi = 1e6, mid;
  while(lo <= hi){
    mid = (lo + hi) / 2;
    if(check(mid)) hi = mid - 1;
    else lo = mid + 1;
  }
  cout << lo;
}

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