# USACO[Elite 2010 February Competition/gold]corral

CODE:

/*

PROG: corral

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Covering the Corral [Richard Peng, 2009]

CONTENT:

The cows are so modest they want Farmer John to install covers

around the circular corral where they occasionally gather. The

corral has circumference C (1 <= C <= 1,000,000,000), and FJ can

choose from a set of M (1 <= M <= 100,000) covers that have fixed

starting points and sizes. At least one set of covers can surround

the entire corral.

Cover i can be installed at integer location x_i (distance from

starting point around corral) (0 <= x_i < C) and has integer length

l_i (1 <= l_i <= C).

FJ wants to minimize the number of segments he must install. What

is the minimum number of segments required to cover the entire

circumference of the corral?

Consider a corral of circumference 5, shown below as a pair of

connected line segments where both ‘0’s are the same point on the

corral (as are both 1’s, 2’s, and 3’s).

Three potential covering segments are available for installation:

Start   Length

i     x_i     l_i

1      0       1

2      1       2

3      3       3

0   1   2   3   4   0   1   2   3

corral: +—+—+—+—+–:+—+—+—+- …

11111               1111

22222222            22222222

333333333333

|………………|

As shown, installing segments 2 and 3 cover an extent of (at least)

five units around the circumference. FJ has no trouble with the

overlap, so don’t worry about that.

PROBLEM NAME: corral

INPUT FORMAT:

* Line 1: Two space-separated integers: C and M

* Lines 2..M+1: Line i+1 contains two space-separated integers: x_i

and l_i

SAMPLE INPUT (file corral.in):

5 3

0 1

1 2

3 3

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of segments

required to cover all segments of the circumference of the

corral

SAMPLE OUTPUT (file corral.out):

2

*/

#include <stdio.h>

const int MAXM=100000;

int C,M;

int x[MAXM],l[MAXM];

int right[MAXM];

int f[MAXM];

void quick_sort(int L,int R)

{

int x_mid=x[(L+R)>>1];

int l_mid=l[(L+R)>>1];

int i=L,j=R;

while (i<=j)

{

while ((x[i]<x_mid)||(x[i]==x_mid&&x[i]+l[i]>x_mid+l_mid)) i++;

while ((x[j]>x_mid)||(x[j]==x_mid&&x[j]+l[j]<x_mid+l_mid)) j–;

if (i<=j)

{

int swap;

swap=x[i];

x[i]=x[j];

x[j]=swap;

swap=l[i];

l[i]=l[j];

l[j]=swap;

i++;

j–;

}

}

if (L<j) quick_sort(L,j);

if (i<R) quick_sort(i,R);

}

int main()

{

freopen(“corral.in”,“r”,stdin);

freopen(“corral.out”,“w”,stdout);

scanf(“%d %d\n”,&C,&M);

for (int i=0;i<M;i++)

scanf(“%d %d\n”,&x[i],&l[i]);

quick_sort(0,M-1);

for (int i=0,j=0;j<M;)

{

x[i]=x[j];

l[i]=l[j];

j++;

while ((x[i]+l[i]>=x[j]+l[j])&&(j<M)) j++;

i++;

if (j>=M) M=i;

}

//for (int i=0;i<M;i++)

//    printf(“%d %d\n”,x[i],x[i]+l[i]);

for (int i=M-1,j=M-1;i>=0;i–)

{

while ((x[j]>x[i]+l[i])&&(j>=0)) j–;

right[i]=j;

}

for (int begin=M-1;;begin–)

{

if (x[begin]+l[begin]<C) break;

int X=x[begin]+l[begin]-C;

int L=x[begin]-X;

if (L<=0)

{

break;

}

//printf(“begin:%d\n”,begin);

//printf(“X=%d X+L=%d\n”,X,X+L);

f[begin]=1;

for (int i=begin-1,j=begin;i>=0;i–)

{

//while (x[j]>x[i]+l[i]) j–;

//printf(“i%d j%d\n”,i,j);

f[i]=f[right[i]]+1;

//f[i]=f[j];

//for (int k=j;k>i;k–)

//    if (f[i]>f[k])

//       f[i]=f[k];

//f[i]++;

if (x[i]<=X)

{

//printf(“begin:%d f[%d]=%d\n”,begin,i,f[i]);

break;

}

}

}

fclose(stdin);

fclose(stdout);

return 0;

}