 #include <cassert>
#include <algorithm>

using namespace std;

int dist(int a, int b, int L) {
  a -= b;
  if (a < 0) a += L;
  if (a > L - a) a = L - a;
  return a;
}

struct rect {
  int from1, to1;
  int from2, to2;
  int who;
  int count;
};

struct event {
  int x, start, y;
};

int const M = 1234567;
int const N = 123456;
int L;
int fw[M];

void add(int x, int y) {
  for (int i = x; i < L; i |= i + 1) fw[i] += y;
}

int getsum(int x) {
  int ret = 0;
  for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
    ret += fw[i];
  }
  return ret;
}

int getsum(int l, int r) {
  return getsum(r) - getsum(l - 1);
}

int a[N], b[N], order[N], f[N];
rect rs[3 * N];
event events[7 * N];

int main() {
  int n;
  assert(2 == scanf("%d%d", &n, &L));
  for (int i = 0; i < n; i++) {
    assert(2 == scanf("%d%d", a + i, b + i));
    if (a[i] > b[i]) swap(a[i], b[i]);
    order[i] = i;
    f[i] = dist(a[i], b[i], L);
  }
  int l = 0;
  int r = L / 4 + 1;
  while (l < r - 1) {
    int mid = (l + r) >> 1;
    int cn = 0;
    for (int i = 0; i < n; i++) {
      if (f[i] < mid) continue;
      if (f[i] >= 2 * mid && b[i] + mid < L) {
        rs[cn++] = {a[i] + mid, b[i] - mid, b[i] + mid, min(L - 1, a[i] + L - mid), i, 0};
      }
      if (b[i] + 2 * mid < L) {
        rs[cn++] = {b[i] + mid, min(L - 1, a[i] + L - mid), b[i] + mid, min(L - 1, a[i] + L - mid), i, 0};
      }
      if (a[i] >= mid && b[i] + mid < L) {
        rs[cn++] = {0, a[i] - mid, b[i] + mid, L - 1, i, 0};
      }
    }
    int en = 0;
    for (int i = 0; i < cn; i++) {
      events[en++] = {rs[i].from1, -1, i};
      events[en++] = {rs[i].to1, 1, i};
    }
    for (int i = 0; i < n; i++) {
      if (f[i] < mid) continue;
      events[en++] = {a[i], 0, b[i]};
    }
    sort(events, events + en, [](event const &e1, event const &e2) {
      if (e1.x != e2.x) return e1.x < e2.x;
      return e1.start < e2.start;
    });
    for (int i = 0; i < L; i++) fw[i] = 0;
    bool found = false;
    for (int it = 0; it < en; it++) {
      event &e = events[it];
      if (e.start == -1) {
        rect &cr = rs[e.y];
        cr.count -= getsum(cr.from2, cr.to2);
      } else if (e.start == 0) {
        add(e.y, 1);
      } else {
        rect &cr = rs[e.y];
        cr.count += getsum(cr.from2, cr.to2);
        if (cr.count > 0) {
          found = true;
          break;
        }
      }
    }
    if (found) {
      l = mid;
    } else {
      r = mid;
    }
  }
  printf("%d\n", l);
}

created 1 year ago by Joba

C Language online compiler

Write, Run & Share C Language code online using OneCompiler's C online compiler for free. It's one of the robust, feature-rich online compilers for C language, running the latest C version which is C18. Getting started with the OneCompiler's C editor is really simple and pretty fast. The editor shows sample boilerplate code when you choose language as 'C' and start coding!

Read inputs from stdin

OneCompiler's C online editor supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample C program which takes name as input and print your name with hello.

#include <stdio.h>
int main()
{
    char name[50];
    printf("Enter name:");
    scanf("%s", name);
    printf("Hello %s \n" , name );
    return 0;
    
}

About C

C language is one of the most popular general-purpose programming language developed by Dennis Ritchie at Bell laboratories for UNIX operating system. The initial release of C Language was in the year 1972. Most of the desktop operating systems are written in C Language.

Key features:

Structured Programming
Popular system programming language
UNIX, MySQL and Oracle are completely written in C.
Supports variety of platforms
Efficient and also handle low-level activities.
As fast as assembly language and hence used as system development language.

Syntax help

Loops

1. If-Else:

When ever you want to perform a set of operations based on a condition if-else is used.

if(conditional-expression) {
   // code
} else {
   // code
}

You can also use if-else for nested Ifs and if-else-if ladder when multiple conditions are to be performed on a single variable.

2. Switch:

Switch is an alternative to if-else-if ladder.

switch(conditional-expression) {    
case value1:    
 // code    
 break;  // optional  
case value2:    
 // code    
 break;  // optional  
...    
    
default:     
 // code to be executed when all the above cases are not matched;    
}

3. For:

For loop is used to iterate a set of statements based on a condition.

for(Initialization; Condition; Increment/decrement){  
  // code  
}

4. While:

While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.

while(condition) {  
 // code 
}

5. Do-While:

Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.

do {
  // code 
} while (condition);

Arrays

Array is a collection of similar data which is stored in continuous memory addresses. Array values can be fetched using index. Index starts from 0 to size-1.

Syntax

One dimentional Array:

data-type array-name[size];

Two dimensional array:

data-type array-name[size][size];

Functions

Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity.

Two types of functions are present in C

Library Functions:

Library functions are the in-built functions which are declared in header files like printf(),scanf(),puts(),gets() etc.,

User defined functions:

User defined functions are the ones which are written by the programmer based on the requirement.

How to declare a Function

return_type function_name(parameters);

How to call a Function

function_name (parameters)

How to define a Function

return_type function_name(parameters) {  
  //code
}